好久没更了 = =

现在看到什么题都感觉一脸不可做，水平太低了

题意

给出仅包含小写字母的长度为 $n$ 的字符串 $s$

每次取出 $s$ 的一个子串 $t_i$（可以为空），执行 $m$ 次，顺次拼接成一个大字符串 $t=t_1 t_2\dots t_m$，求可以得到多少种本质不同的 $t$

$q$ 次询问，每次给出一个 $m$

$n,q\le 10^5, m\le 10^{10}$

UOJ #299

题意

小 R 和小 B 玩了 $n$ 局游戏，第一局小 R 获胜的概率是 $p_1$，对于第 $i(1<i\le n)$ 局，若第 $i-1$ 局小 R 获胜，则小 R 获胜的概率为 $p_i$，否则为 $q_i$

现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 $m$ 次增加或删除已知条件后都输出答案

$n,m\le 2\times 10^5$

后面的游戏结果会影响前面的概率 = =

Codeforces 755G. PolandBall and Many Other Balls

题意

有 $n$ 个球编号为 $1,2,\dotsc,n$，一组可以是一个球 ${i}$ 或者是两个相邻的球 ${i,i+1}$

对于 $i=1,2,\dotsc,k$ 求 $n$ 个球划分成 $i$ 组的方案数，每个球至多在一个组内，并且可以不在任何一个组内

对 $998244353$ 取模

$n\le 10^9,k\le 2^{15}$

LOJ #2269

题意

你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

• Change x y，表示把第$x$个点的权值改成$y$

• Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$

$n,q\le30000,m\le128$

引入

在有些dp中，转移可以用一种具有结合律的变换描述，并且可以快速合并

因此我们使用数据结构维护，来支持修改并快速得到全局或某个子结构的dp值