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\n",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\n",ans);

	}

	return 0;

}

巴特西

codeforces 932E Team Work（组合数学、dp）

codeforces 932E Team Work

题意

题解

解法一

解法二

解法三

解法四

解法五

代码

解法一

解法二

最新文章

热门文章