思路
第二类斯特林数和组合数推式子的题目
题目要求\(\sum_{i=1}^n \left(\begin{matrix}n \\ i \end{matrix} \right) i^k\)
一个性质
第二类斯特林数有这样的性质
\[n^k=\sum_{i=0}^n \left\{\begin{matrix}k \\ i \end{matrix} \right\}i!\left(\begin{matrix}n \\ i \end{matrix} \right)
\]
\]
就是相当于枚举取哪i个可区分的盒子，再把k个球放进去，方案数总和就等于每个球都任意放的方案数
推式子
因为\(i=0\)时，后面的贡献是0，所以不妨变为\(\sum_{i=0}^n \left(\begin{matrix}n \\ i \end{matrix} \right) i^k\)
然后代入性质，得到
\[\begin{align}&\sum_{i=0}^n \left( \begin{matrix}n\\i\end{matrix}\right)i^k \\ =&\sum_{i=0}^n \left( \begin{matrix}n\\i\end{matrix}\right)\sum_{j=0}^i \left\{ \begin{matrix}k\\j\end{matrix}\right\}j!\left( \begin{matrix}i\\j\end{matrix}\right) \\=&\sum_{i=0}^n \left( \begin{matrix}n\\i\end{matrix}\right)\sum_{j=0}^i \left\{ \begin{matrix}k\\j\end{matrix}\right\}\frac{i!}{(n-j)!}\\=&n!\sum_{i=0}^n \frac{1}{(n-i)!}\sum_{j=0}^i \left\{ \begin{matrix}k\\j\end{matrix}\right\}\frac{1}{(n-j)!}\\=&n!\sum_{i=0}^n \sum_{j=0}^i \left\{ \begin{matrix}k\\j\end{matrix}\right\}\frac{1}{(n-i)!(n-j)!}\\=&n!\sum_{j=0}^n\left\{ \begin{matrix}k\\j\end{matrix}\right\} \sum_{i=j}^n\left( \begin{matrix}n-i\\n-j\end{matrix}\right) \frac{1}{(n-j)!} \\=&n!\sum_{i=0}^n \sum_{j=0}^i \left\{ \begin{matrix}k\\j\end{matrix}\right\}\frac{1}{(n-i)!(n-j)!}\\=&\sum_{j=0}^n\frac{n!}{(n-j)!}\left\{ \begin{matrix}k\\j\end{matrix}\right\} \sum_{i=j}^n\left( \begin{matrix}n-i\\n-j\end{matrix}\right)\\=&\sum_{j=0}^n\frac{n!}{(n-j)!}\left\{ \begin{matrix}k\\j\end{matrix}\right\} \sum_{i=0}^n\left( \begin{matrix}n-i\\n-j\end{matrix}\right) \\=&\sum_{j=0}^n\frac{n!}{(n-j)!}\left\{ \begin{matrix}k\\j\end{matrix}\right\}2^{n-j}\\=&\sum_{j=0}^k\frac{n!}{(n-j)!}\left\{ \begin{matrix}k\\j\end{matrix}\right\}2^{n-j}\end{align}
\]
\]
然后\(O(k^2)\)的处理就好了
代码
不知道为什么n,k不能声明到S函数的上方
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1000000007;
int s[5010][5010]={0};
bool vis[5010][5010]={0};
int my_pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(1LL*ans*a)%MOD;
a=(1LL*a*a)%MOD;
b>>=1;
}
return ans;
}
int S(int n,int k){
// printf("n=%lld k=%lld\n",n,k);
if(vis[n][k])
return s[n][k];
vis[n][k]=true;
if(n==0&&k==0)
return s[n][k]=1;
else if(n==0||k==0)
return s[n][k]=0;
return s[n][k]=(S(n-1,k-1)%MOD+k*S(n-1,k)%MOD)%MOD;
}
int n,k;
signed main(){
scanf("%lld %lld",&n,&k);
// printf("%lld %lld\n",n,k);
int ans=0;
int mid=1;
for(int i=0;i<=min(k,n);i++){
ans=(ans+mid*S(k,i)%MOD*my_pow(2,n-i)%MOD)%MOD;
mid=(mid*(n-i))%MOD;
}
printf("%lld\n",ans);
return 0;
}