还没很深刻地理解，先瞎写一通。
P4548 [CTSC2006] 歌唱王国
设 表示答案等于 的 PGF， 表示答案大于 的 PGF，容易有 ，于是 ，即 。
我们要求的即为 ，代入之后得到 ，于是有 。
我们尝试建立 与 的关系，考虑这样一个事件：
当前随机了 个字符，还没出现 。
再去随机 个字符，这些字符恰好构成了 。
我们分别用 和 去刻画这个事件的概率 ，首先不难得到 ，因为上下两个条件是独立的，其次我们考虑最终的字符串中 出现的位置的所有情况，容易发现 有可能出现在位置 （这里指以 结尾）当且仅当 是 的一个 border，于是 。
根据两式相等进行化简，我们得出 和 的关系为：
根据定义，，于是代入 即得 ，可以线性求出。
ARC136F Flip Cells
设 表示 次操作后从初始状态到达目标状态的 PGF， 表示 次操作后从目标状态到达目标状态的 PGF， 表示答案的 PGF，所求即为 。
容易得到 ，于是 ，所以 。
不难发现 本质相同，我们只考虑如何求 和 。
考虑单个格子的 PGF， 的 次项系数表示该格子被操作了 次的概率，令 ，则我们有 ，发现某个格子的状态只与被操作次数的奇偶性有关，于是我们设 ， 同理，则我们发现 的 EGF 其实就是一堆格子 PGF 对应的 EGF 乘起来（使用 EGF 的原因是因为操作是有顺序的）。于是有：
其中 表示恰好翻转 个格子到达目标状态的方案数，容易 dp 求出。
根据 ，我们容易得出 和 的封闭形式，即：
将其带入上述式子，二项式定理展开得：
将后面的式子表示成 OGF，即：
后面部分容易预处理出，设其为 ，代回原式子化成 OGF 形式得：
代入 即为答案，注意当 时会出现分母上有 的情况，我们转而计算 即可，此时答案为 。
总时间复杂度为 。