CF932 E. Team Work
题意
求
\[\sum_{i=0}^n\binom{n}{i}i^k
\]
\]
其中\(n\le 10^9,k\le 5000\)，对\(mod=998244353\)取模
事实证明我斯特林数学到狗身上去了...
关于斯特林数的一个常用公式是
\[x^n=\sum_{i=1}^x\binom{x}{i}{n \brace i}i!
\]
\]
然后带进去推一波式子就完事了
\[\begin{aligned}
\sum_{i=0}^n\binom{n}{i}i&=\sum_{i=0}^n\binom{n}{i}\sum_{j=1}^k\binom{i}{j}{k\brace j}j!\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\binom{n}{i}\binom{i}{j}j!\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\frac{n!}{(n-i)!(i-j)!}\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\frac{n!(n-j)!}{(n-i)!(i-j)!(n-j)!}\\
&=\sum_{j=1}^k{k \brace j}n^{\underline j}\sum_{i=0}^n\binom{n-j}{n-i}\\
&=\sum_{j=1}^k{k \brace j}n^{\underline j}2^{n-j}
\end{aligned}
\]
\sum_{i=0}^n\binom{n}{i}i&=\sum_{i=0}^n\binom{n}{i}\sum_{j=1}^k\binom{i}{j}{k\brace j}j!\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\binom{n}{i}\binom{i}{j}j!\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\frac{n!}{(n-i)!(i-j)!}\\
&=\sum_{j=1}^k{k \brace j}\sum_{i=0}^n\frac{n!(n-j)!}{(n-i)!(i-j)!(n-j)!}\\
&=\sum_{j=1}^k{k \brace j}n^{\underline j}\sum_{i=0}^n\binom{n-j}{n-i}\\
&=\sum_{j=1}^k{k \brace j}n^{\underline j}2^{n-j}
\end{aligned}
\]
Code:
#include <cstdio>
const int mod=1e9+7;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
#define mul(x,y) (1ll*(x)*(y)%mod)
inline int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int str[5010][5010],n,k,ans;
int main()
{
scanf("%d%d",&n,&k);
str[0][0]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<=i;j++)
str[i][j]=add(str[i-1][j-1],mul(str[i-1][j],j));
for(int i=1,f=1;i<=n&&i<=k;i++)
{
f=mul(f,n-i+1);
ans=add(ans,mul(f,mul(str[k][i],qp(2,n-i))));
}
printf("%d\n",ans);
return 0;
}
2019.3.27