和式处理——扰动法
[BZOJ3157] 国王奇遇记
题意：给定 \(n\)，\(m\)，设 \(S_p=\sum_{i=1}^ni^pm^i\)，求 \(S_m\)。
\[S_p+(n+1)^{p}m^{n+1}=\sum_{i=1}^{n+1}i^pm^i=1^pm^1+\sum_{i=2}^{n+1}i^pm^i=m+\sum_{i=1}^n(i+1)^pm^{i+1}
\]
\[=m+m\sum_{i=1}^n(i+1)^pm^{i}=m+m\sum_{i=1}^n\sum_{j=0}^p\binom{p}{j}i^jm^i=m+m\sum_{j=0}^p\binom{p}{j}\sum_{i=1}^ni^jm^i
\]
\[\Rightarrow S_p+(n+1)^{p}m^{n+1}=m+m\sum_{j=0}^p\binom{p}{j}S_j=m+m\sum_{j=0}^{p-1}\binom{p}{j}S_j+mS_p
\]
\[\Rightarrow S_p=\frac{(n+1)^{p}m^{n+1}-m-m\sum_{j=0}^{p-1}\binom{p}{j}S_j}{m-1}
\]
当 \(m=1\) 时需要特判，直接输出 \(S_m=\sum_{i=1}^ni=\frac{n(n+1)}{2}\)。
[Luogu P4948] 数列求和
题意：给定 \(n\)，\(a\)，\(k\)，设 \(S_p=\sum_{i=1}^ni^pa^i\)，求 \(S_k\)。
只需要将上一道题推理过程中的 \(m\) 换成 \(a\) 即可，同样在 \(a=1\) 时需要进行特判：
\[S_p+(n+1)^p=\sum_{i=1}^{n+1}i^p=1+\sum_{i=2}^{n+1}i^p=1+\sum_{i=1}^{n}(i+1)^p=1+\sum_{i=1}^n\sum_{j=0}^p\binom{p}{j}i^j
\]
\[=1+\sum_{j=0}^p\binom{p}{j}\sum_{i=1}^ni^j=1+\sum_{j=0}^p\binom{p}{j}S_j=1+\sum_{j=0}^{p-1}\binom{p}{j}S_j+S_p
\]
\[\Rightarrow (n+1)^p=1+\sum_{j=0}^{p-1}\binom{p}{j}S_j\Rightarrow S_{p-1}=\frac{(n+1)^p-1-\sum_{j=0}^{p-2}\binom{p}{j}S_j}{p}
\]
\[\Rightarrow S_{p}=\frac{(n+1)^{p+1}-1-\sum_{j=0}^{p-1}\binom{p+1}{j}S_j}{p+1}
\]
斯特林数进阶
发挥工科优势，上升下降幂与普通幂的转化：
\[x^\overline{n}=\sum^{n}_{k=0}{n\brack k}x^k
\]
\[x^n=\sum_{k=0}^n{n\brace k}(-1)^{n-k}x^{\overline{k}}
\]
\[x^n=\sum_{k=0}^n{n\brace k}x^\underline{k}
\]
\[x^{\underline{n}}=\sum_{k=0}^n{n\brack k}(-1)^{n-k}x^k
\]
一个需要理解组合意义的式子：
\[x^n=\sum_{k=0}^{n\operatorname{or} x}\binom{x}{k}{n\brace k}k!
\]
左：\(x\) 个盒子放 \(n\) 个球的方案数。
右：在 \(x\) 个盒子里选 \(k\) 个盒子为非空，再把 \(n\) 个球放进去，乘上 \(k!\) 表示给盒子标上号。
[省选联考 2020 A 卷] 组合数问题
题意：求 \(\sum_{k=0}^{n}f(k)x^k\binom{n}{k}\)，其中 \(f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m\)
\[\sum_{k=0}^{n}\sum_{i=0}^ma_ik^ix^k\binom{n}{k}=\sum_{k=0}^{n}\sum_{i=0}^ma_ik^ix^k\binom{n}{k}
\]
把 \(k_i\) 拆掉：
\[=\sum_{k=0}^{n}\sum_{i=0}^ma_i\sum_{j=0}^k\binom{k}{j}{i\brace j}j!x^k\binom{n}{k}=\sum_{i=0}^ma_i\sum_{k=0}^{n}x^k\sum_{j=0}^k\binom{n}{k}\binom{k}{j}{i\brace j}j!
\]
\[=\sum_{i=0}^ma_i\sum_{k=0}^{n}x_k\sum_{j=0}^k\binom{n}{j}\binom{n-j}{k-j}{i\brace j}j!=\sum_{i=0}^ma_i\sum_{j=0}^n\binom{n}{j}{i\brace j}j!\sum_{k=j}^{n}x^k\binom{n-j}{k-j}
\]
\[=\sum_{i=0}^ma_i\sum_{j=0}^n\binom{n}{j}{i\brace j}j!\sum_{k=0}^{n-j}x^{k+j}\binom{n-j}{k}=\sum_{i=0}^ma_i\sum_{j=0}^n\binom{n}{j}{i\brace j}j!x_j\sum_{k=0}^{n-j}x^{k}\binom{n-j}{k}
\]
\[=\sum_{i=0}^ma_i\sum_{j=0}^n\binom{n}{j}{i\brace j}j!x_j\sum_{k=0}^{n-j}x^{k}\binom{n-j}{k}1^{n-j-k}=\sum_{i=0}^ma_i\sum_{j=0}^n\binom{n}{j}{i\brace j}j!x_j(x+1)^{n-j}
\]
发现最后 \(\sum_{j=0}^n\) 中 \(i\brace j\) 要 \(j\leq i\) 时才有意义，所以最终式子：
\[\sum_{i=0}^ma_i\sum_{j=0}^i\binom{n}{j}{i\brace j}j!x_j(x+1)^{n-j}
\]
可以在 \(O(m^2)\) 的时间范围内进行求解。