我生成函数大法终于有用武之地了，但是最后因为分治 FFT 常数太大没过，就很气人，回来试试多项式求逆吧。

Description

给定一个多项式 $f(n)$ 和一个有理数 $r$ 满足 $r \in (0,1)$，求
$$ \sum_{i = 0}^\infty f(n)r^n \mod 9982443533 $$

Solution

显然，如果我们对于某一个 $m$，我们能求出 $\sum\limits_{i = 0}^\infty i^mr^i$，那么我们就能直接解决这个问题了。

我们抛开上面的 $f(x)$，另外设一个 $f_m(r) = \sum\limits_{i = 0}^\infty i^mr^i$，我们有

$$ f_m(r) = \sum_{i = 0}^\infty i^mr^i $$

$$ rf_m(r) = \sum_{i = 1}^\infty (i - 1)^mr^i $$

上边两式相减，得到：

$$ (1 - r)f_m(r) = r\sum_{i = 0}^\infty((i + 1)^m - i^m)r^i $$

把 $(i + 1)^m$ 二项式展开并把 $(1 - r)$ 除过去我们可以得到：

$$ f_m(r) = \frac{r}{1 - r}\sum_{i = 0}^\infty\sum_{k = 0}^{m - 1}C_m^ki^kr^i $$

$$ \frac{f_m(r)}{m!} = \frac{r}{1 - r}\sum_{k = 0}^{m - 1}\frac{1}{(m - k)!}\frac{\sum_{i = 0}^\infty i^kr^i}{k!} $$

注意到 $f_k(r) = \sum\limits_{i = 0}^\infty i^kr^i$

我们可以得到

$$ \frac{f_m(r)}{m!} = \frac{r}{1 - r}\sum_{k = 0}^{m - 1}\frac{1}{(m - k)!}\frac{f_k(r)}{k!} $$

我们可以用分治 FFT 来求出 $\frac {f_k(r)}{k!}$ 就好了。

不过 T 掉了，可以试试多项式求逆来算这个东西，复杂度少一个 $\log$。