题目描述
给出 $n$ 以及一个 $m$ 次多项式 $f(x)$，需要求出
$$sum_{i=0}^n inom{n}{i} f(i)$$
对 $998244353$ 取模的结果。
数据范围
$1le mle 100000,mle nle 10^9$
题解
orzsz！
考虑组合意义，即有 $n$ 个小球，选出 $i$ 个小球的价值为 $f(i)$ 。我们可以记 $x^j$ 的系数的总和，最后再乘上 $a_j$ 即可。
于是考虑 $ ext{dp}$ ： $f[i][j]$ 表示前i个小球， $x^j$ 的系数总和。考虑转移：若 $i$ 不选，则 $f[i][j]=f[i-1][j]$ ；若 $i$ 选，则考虑到 $(x+1)^j=sum_{k=0}^j inom{j}{k}x^k$ ，所以 $f[i][j]=sum_{k=0}^j inom{j}{k}f[i-1][k]$ 。
发现可以 $ ext{exp}$ ，故效率为 $O(nlog n)$ 。
注意到取对数的多项式中常数项不是 $1$ ，但是特判一下即可。