洛谷5326 [ZJOI2019]开关
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
Luogu LOJ 分析 首先你需要看懂这篇题解。 设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。 ...
Luogu 分析 以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。 设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。 分析一下可以列出这样一个式子 用 KMP / has...