codeforces 932E Team Work
题意
给定 (n(1e9))、(k(5000))。求 (Sigma_{x=1}^{n}C_n^xx^k)。
题解
解法一
官方题解 的做法，网上有很多，就不写了。
解法二
从组合数学的角度入手。
参考博客
我们可以这样理解这个式子 (Sigma_{x=1}^{n}C_n^xx^k) ：有 (n) 种小球，从中选出 (x) 种，再选出 (k) 个小球，这 (k) 个小球只能来自选定的 (x) 种类别。求方案数。
如果我们用 (f[i][j]) 表示 (i) 个小球刚好来自某 (j) 个种类的方案数。那么 (Sigma_{x=1}^{n}C_n^xx^k equiv Sigma_{i=1}^{min(n, k)}f_{k,i}*2^{n-i}) 。
(f_{k,i}*2^{n-i}) 可以这样理解：对于选出的某 (k) 个小球，有多少种选出小球种数的方案。
(f_{i,j}) 的转移如下：(f_{i,j}=j*f_{i-1,j}+(n-(j-1))*f_{i-1,j-1})
//
今天看到一个理解（k=2时）
假设一个公司n个人，挑x个人出来进行抽奖，抽两次奖的方案数就是(Sigma_{x=1}^{n}C_n^xx^2)
从另一个角度枚举所有方案数：只有一个人中奖：(n2^{n-1}) 有两个人中奖：(n(n-1)2^{n-2})
解法三
官方题解的评论区 laderlappen 的做法
化简给出的式子，得到的新的式子可以用 (dp) 求解。
解法四
化简之后，变成一个和斯特林数有关的式子。
解法五
官方题解的评论区 _rqy 和 retrograd 的做法
(ans(n, k)=2^n*f_k(n))， (f_k(n)) 是一个 (k) 阶多项式，可以用拉格朗日插值法求出。
代码
解法一
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N=5005, mod=1e9+7;
int n,k;
ll f[N][N];
ll upd(ll &a, ll b) {
a+=b;
if(a>=mod) a-=mod;
}
ll kpow(ll a,ll b) {
ll res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll solve(int a, int b, int c) {
if(~f[a][b]) return f[a][b];
if(a==0) return f[a][b]=kpow(2, c);
ll res=0;
if(c) {
upd(res, b*solve(a-1, b, c)%mod);
upd(res, c*solve(a-1, b+1, c-1)%mod);
} else {
res=kpow(b, a);
}
return f[a][b]=res;
}
int main() {
while(~scanf("%d%d",&n,&k)) {
memset(f,-1,sizeof(f));
printf("%lld
",solve(k, 0, n));
}
return 0;
}
解法二
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N=5005, mod=1e9+7;
int n,k;
ll f[N][N];
ll upd(ll &a, ll b) {
a+=b;
if(a>=mod) a-=mod;
}
ll kpow(ll a,ll b) {
ll res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main() {
while(~scanf("%d%d",&n,&k)) {
memset(f,0,sizeof(f));
f[0][0]=1;
rep(i,1,k+1) {
rep(j,1,min(n, k)+1) {
upd(f[i][j], j*f[i-1][j]%mod);
upd(f[i][j], (n-j+1)*f[i-1][j-1]%mod);
}
}
ll ans=0;
rep(i,1,min(n, k)+1) upd(ans, f[k][i]*kpow(2, n-i)%mod);
printf("%lld
",ans);
}
return 0;
}