问题引入
给出 \(n,k\)，求：
\[\sum_{i=1}^n i^k\dbinom{n}{i}\bmod p \]\(1\le n\le 10^9,1\le k\le 5000,p=10^9+7\)
\(k=0\)
二项式定理：
\[\sum_{i=1}^n \dbinom{n}{i}=2^n-1 \] \(k=1\)
组合恒等式证明
根据组合数的定义，可以推出：
\[\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}\dfrac{n\times (n-1)!}{m\times (m-1)!(n-m)!}=\dfrac{n}{m}\dbinom{n-1}{m-1} \]于是：
\[\sum_{i=1}^n i\dbinom{n}{i}=\sum_{i=1}^ni\times \dfrac{n}{i}\dbinom{n-1}{i-1}=n\sum_{i=0}^{n-1}\dbinom{n-1}{i}=n2^{n-1} \]求导证明
来自《组合数学》。
先带上一个 \(x\)，写成：
\[\sum_{i=1}^n\dbinom{n}{i}x^i=(1+x)^n \]两边同时求导：
\[\sum_{i=1}^ni\dbinom{n}{i}x^{i-1}=n(1+x)^{n-1} \]代入 \(x=1\) 的特殊情况：
\[\sum_{i=1}^ni\dbinom{n}{i}=n2^{n-1} \] \(k=2\)
再导！
观察发现这个 \(i\) 的稳定来源是 \(x^i\) 项求导，因此在上面代入前的式子再乘上一个 \(x\)。
\[\sum_{i=1}^ni\dbinom{n}{i}x^i=n(1+x)^{n-1}x \]导：
\[\sum_{i=1}^ni^2\dbinom{n}{i}x^{i-1}=n[(n-1)(1+x)^{n-2}x+(1+x)^{n-1}] \]代入 \(x=1\) 的特殊情况：
\[\sum_{i=1}^ni^2\dbinom{n}{i}=n[(n-1)2^{n-2}+2^{n-1}]=n(n+1)2^{n-2} \]《组合数学》：通过交替关于 \(x\) 求导并乘以 \(x\)，我们可以得到对于任意 \(k\) 的恒等式，但随着 \(k\) 的增大，将会变得很复杂。
那就先不导剩下情况了。
一个正经的做法
\[\begin{aligned}
&\sum_{i=1}^n i^k\dbinom{n}{i}\\
=&\sum_{i=1}^n\dbinom{n}{i}\sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{i}{j}\\
=&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\dbinom{n}{i}\dbinom{i}{j}\\
=&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\dbinom{n}{j}\dbinom{n-j}{i-j}\\
=&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}\sum_{i=0}^{n-j}\dbinom{n-j}{i}\\
=&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}2^{n-j}
\end{aligned}
\]本题可以 \(O(k^2)\) 预处理第二类 \(\text{Stirling}\) 数做，在模数友好的情况下可以 \(\text{NTT}\) 求一行。
一个不正经的猜想
\(\text{Jijidawang}\)：我觉得它是 \(k\) 次多项式……
我：？
\(\text{Jijidawang}\)：……先除去 \(2^{n-k}\)。
在刚刚的求 \(k=1,2\) 时，的确除 \(2^{n-k}\) 的部分像是 \(k\) 次多项式。
同时在 \(k\) 一定时，上面正经推导后得出的式子：
\[f_k(n)=\dfrac{\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}2^{n-j}}{2^{n-k}}=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}2^{k-j} \]似乎也说明这是一个 \(k\) 次多项式。
目前我们已知 \(k=1,2\) 成立了，做差分试试：
\[\begin{aligned} \Delta f_k(n)=&f_k(n+1)-f_k(n)\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}2^{k-j}[(n+1)^{\underline{j}}-n^{\underline{j}}]\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}2^{k-j}n^{\underline{j-1}}[(n+1)-(n-j+1)]\\ =&\sum_{j=0}^kj\begin{Bmatrix}k\\j\end{Bmatrix}2^{k-j}n^{\underline{j-1}} \end{aligned} \]好像一阶差分可以次数降 \(1\)，那么 \(k\) 次多项式就板上钉钉了。
最后来一发 \(\text{Lagrange}\) 插值看看实力。
点击查看代码
int n,k;
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int Y[5005];
int C[5005][5005],pw[5005];
int fact,fact_inv[5005];
int pw2[5005],inv2=5e8+4;
int pre[5005],suf[5005];
inline int Lagrange(int X){
pre[0]=1,suf[k]=1;
for(int i=1;i<=k;++i) pre[i]=1ll*pre[i-1]*(X-(i-1)+mod)%mod;
for(int i=k-1;i>=0;--i) suf[i]=1ll*suf[i+1]*(X-(i+1)+mod)%mod;
int res=0;
for(int i=0;i<=k;++i){
int now=1ll*Y[i]*pre[i]%mod*suf[i]%mod*fact_inv[i]%mod*fact_inv[k-i]%mod;
if((k-i)&1) res=(res-now+mod)%mod;
else res=(res+now)%mod;
}
return res;
}
int main(){
n=read(),k=read();
C[0][0]=1;
for(int i=1;i<=k;++i){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
for(int i=1;i<=k;++i){
pw[i]=1;
for(int j=1;j<=k;++j){
pw[i]=1ll*pw[i]*i%mod;
}
}
fact=1,fact_inv[0]=1;
for(int i=1;i<=k;++i) fact=1ll*fact*i%mod;
fact_inv[k]=q_pow(fact,mod-2,mod);
for(int i=k-1;i>=1;--i) fact_inv[i]=1ll*fact_inv[i+1]*(i+1)%mod;
pw2[0]=q_pow(2,k,mod);
for(int i=1;i<=k;++i) pw2[i]=1ll*pw2[i-1]*inv2%mod;
for(int i=1;i<=k;++i){
for(int j=1;j<=i;++j){
Y[i]=(Y[i]+1ll*C[i][j]*pw[j]%mod)%mod;
}
Y[i]=1ll*Y[i]*pw2[i]%mod;
}
printf("%lld\n",1ll*Lagrange(n)*q_pow(2,(n-k+mod-1)%(mod-1),mod)%mod);
return 0;
}
通过了，实锤了。
最终章·导
前情提要：全是 \(\text{Dirty Work}\)，建议不阅读。
\(k=3\) 的情况：
\[\begin{aligned} &[n(n-1)(1+x)^{n-2}x^2+n(1+x)^{n-1}x]'\\ =&n(n-1)(n-2)(1+x)^{n-3}x^2+2n(n-1)(1+x)^{n-2}x+n(n-1)(1+x)^{n-2}x+n(1+x)^{n-1}\\ =&n(n-1)(n-2)(1+x)^{n-3}x^2+3n(n-1)(1+x)^{n-2}x+n(1+x)^{n-1}\\ \end{aligned}\]长得还挺工整的，每次求导只增加一项，剩下可以合并。
\[\sum_{i=1}^ni^k\dbinom{n}{i}x^{i-1}=\sum_{i=1}^ka_{k,i}\times n^{\underline{i}}(1+x)^{n-i}x^{i-1} \]乘完了 \(x\)，导：
\[\begin{aligned} &\left(\sum_{i=1}^ka_{k,i}\times n^{\underline{i}}\times (1+x)^{n-i}x^i\right)'\\ =&\sum_{i=1}^ka_{k,i}\times \left(n^{\underline{i+1}}\times (1+x)^{n-(i+1)}x^{i-1}+i\times n^{\underline{i}}\times (1+x)^{n-i}x^{i-1}\right)\\ =&\sum_{i=1}^{k+1}(a_{k,i-1}+i\times a_{k,i})\times n^{\underline{i}}(1+x)^{n-i}x^{i-1} \end{aligned} \]于是系数满足：
\[a_{k+1,i}=a_{k,i-1}+i\times a_{k,i} \]结束。（有其他东西或许还会再更）
标签：begin,end,dbinom,求和,闲话,sum,2023.2,int,Bmatrix From： https://www.cnblogs.com/SoyTony/p/Flowers_on_Feb_3rd_2023.html