[题解] [P3711] 仓鼠的数学题

给定 $n$ 和 长度为 $n+1$ 的数组 $a_0\cdots a_n$，求

$$
\sum_{k=0}^n a_k\sum_{i=0}^x i^k
$$

的各项系数（共 $n+2$ 项）。$1\le n\le 250000$，答案对 $998244353$ 取模。

题目链接

---

思路

我们令 $S_{n,k}=\sum_{i=0}^{n-1}i^k$，然后我们考虑求出 $S_{n,k}$ 关于 $k$ 的 指数生成函数 $S_n(x)$：

$$ \begin{aligned} S_n(x)&=\sum_{k=0}^\infty \frac{x^k}{k!}\sum_{i=0}^{n-1} i^k\\ &=\sum_{i=0}^{n-1}\sum_{k=0}^\infty \frac{(xi)^k}{k!}\\ &=\sum_{i=0}^{n-1}(e^x)^i\\ &=\frac{e^{nx}-1}{e^x-1} \end{aligned} $$

考虑怎么拿到这个东西的第 $k$ 项系数。先设 $B(x)=\frac{x}{e^x-1}$，于是有：

$$ \begin{aligned} S_n(x)&=\frac{e^{nx}-1}{x}\cdot B(x)\\ S_n(x)&=\left(\sum_{i=0}^\infty \frac{n^{i+1}}{(i+1)!}x^i\right)\cdot B(x)\\ \frac{S_{n,k}}{k!}&=\sum_{i=0}^k \frac{n^{i+1}}{(i+1)!}\cdot\frac{B_{k-i}}{(k-i)!} \end{aligned} $$

然后我们转换原式（由于我们只求到了 $n-1$ 所以要加上 $n^k$）：

$$ \begin{aligned} &\sum_{k=0}^n a_k\sum_{i=0}^x i^k\\ =&\sum_{k=0}^n a_k\left(x^k+S_{x,k}\right)\\ =&\sum_{k=0}^n a_k\left(x^k+k!\sum_{i=0}^k \frac{x^{i+1}}{(i+1)!}\cdot\frac{B_{k-i}}{(k-i)!}\right)\\ =&\left(\sum_{k=0}^n a_k x^k\right)+\sum_{i=0}^n\frac{x^{i+1}}{(i+1)!}\sum_{k=i}^n a_k k!\frac{B_{k-i}}{(k-i)!} \end{aligned} $$

然后记 $B'_i=B_{n-i}$，然后上面右边那个式子就可以卷积了。

为看到的题解区里面一位把 $(n+1)$ 带入上面式子然后二项式定理展开的可怜老哥默哀

要注意的一个细节是怎么求 $B$。上文提到 $B=\frac{x}{e^x-1}$， 但是直接多项式求逆会发现由于 $(e^x-1)$ 常数项为 0，没法求逆，考虑把上面的 $x$ 弄下来，然后得到：
$$
B=\frac{1}{\sum_{i=0}^\infty \frac{x^i}{(i+1)!}}
$$
然后就可做了。顺带一提，这里的 $B$ 就是多数题解里面提到的伯努利数。

代码

mivik.h

代码