Codeforces463-E.Team Work
题意：求
\[\sum_{i=1}^n \binom{n}{i} i^k
\]
其中\(1\leq n\leq 10^9\)，\(1\leq k \leq 5000\)。
题解：
其实这个题\(k\)的数据范围就已经暗示了做法的复杂度——应该是要去考虑根据 \(k\) 去递推了。
首先为了方便，\(i=0\)这一项完全可以补上，用类似生成函数的想法，补上一个\(x\)占位：
\[f_k(x)=\sum_{i=0}^n\binom{n}{i} i^k x^i
\]
我们如果知道\(f_k(x)\)的封闭形式，只要代入\(x=1\)就能求了，而\(f_k\)的递推应该是很经典的：
\[xf_k'(x)=\sum_{i=0}^n\binom{n}{i} i^{k+1} x^i=f_{k+1}(x)
\]
即\(f_{k+1}(x)=x f'_k(x)\)，边界是\(f_0(x)=\sum_{i=0}^n \binom{n}{i} x^i=(x+1)^n\)，而递推中的运算只有求导和乘法。
\[x[(x+1)^n]'=n\times x(x+1)^{n-1}
\]
设\(f=x^a (x+1)^b\)，则
\[xf'=ax^a (x+1)^b +b x^{a+1}(x+1)^{b-1}
\]
求导过程中\(a+b\)的值是不变的。
设个dp数组\(g[k][b]\)表示\(f_k(x)\)中\(x^{n-b}(x+1)^b\)的系数是多少，边界是\(g[k][n]=1\)，需要推出\(g[0][n-k\dots n]\)的系数，所以只需要从\(g[i][j]\) 转移给\(g[i-1][j]\) 和\(g[i-1][j-1]\)，最后的答案就是\(\sum_j g[0][j]\times 2^j\)。
顺便这题应该是要写滚动数组，\(5000^2\)可能MLE。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int N=5005;
const int MOD=1e9+7;
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int ksm(int a,int b){
int ret=1;
for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;
return ret;
}
int n,k,g[N][2];
int main(){
fastio;
cin>>n>>k;
int D=n-k-1,st=(k&1),lwb=max(0,n-k);
g[n-D][st]=1;
for(int i=k;i>=1;i--){
int c=(i&1);
rep(j,lwb,n){
add(g[j-D][c^1],(ll)(n-j)*g[j-D][c]%MOD);
if(j)add(g[j-1-D][c^1],(ll)j*g[j-D][c]%MOD);
}
rep(j,lwb,n)g[j-D][c]=0;
}
int ans=0;
rep(j,lwb,n)add(ans,(ll)g[j-D][0]*ksm(2,j)%MOD);
cout<<ans;
return 0;
}