[ICM Technex 2018 and Codeforces Round #463][Codeforces 932E] Team Work

    题目大意：\(1 \leq n \leq 10^9, 1 \leq k \leq 1000 \),求\[ \sum_{i=1}^n{C_n^i \cdot i^k}\]

    题解：这题直接强推公式会很困难，但是如果能注意到这一点的话会很好做：设\(F(k) = \sum_{i=1}^n{i^k C_n^i x^i}\)，那么有\(F'(k) = \sum_{i=1}^n{i^{k+1} C_n^i x^{i-1}}\)，然后可以推出\(xF'(k) = \sum_{i=1}^n{i^{k+1} C_n^i x^i}\)，取\(x=1\)，就是我们所求的东西。

    构造出生成函数，然后一项项求导就可以从\(F(k)\)得到\(F(k+1)\)。初始时有\(F(1) = nx(1+x)^{n-1}\)。由于最多只会产生\(k\)项（每一项的形式为\(a_i x^i (1+x)^{n-i}\)，求导后为\(i \cdot a_i x^{i-1} (1+x)^{n-i} + (n-i) \cdot a_i x^i (1+x)^{n-i-1}\)），所以时间复杂度是\(O(k^2)\)的。

#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int mo=1e9+7;

int Pow(int x,int p)
{
	long long xx=x,res=1;
	while (p)
	{
		if (p&1) (res*=xx)%=mo;
		(xx*=xx)%=mo;
		p>>=1;
	}
	return res;
}

int add(int x,int y) {return (x+y)%mo;}
int mul(int x,int y) {return ((long long)x*y)%mo;}

int f[maxn][maxn];
int n,k,ans;

int main()
{
	scanf("%d%d",&n,&k);
	f[1][1]=n;
	for (int i=2;i<=k;i++)
	for (int j=1;j<=min(i,n);j++)
		f[i][j]=add(mul(f[i-1][j],j),mul(f[i-1][j-1],n-j+1));
	for (int i=min(k,n),k2=Pow(2,n-i);i>=1;i--)
		ans=add(ans,mul(f[k][i],k2)),k2=mul(k2,2);
	printf("%d\n",ans);
	return 0;
}