CF 932E Team Work

题目大意：求\(\sum\limits_{i=0}^{n}C_{n}^{i}i^{k}\)。

我们根据套路\(n^{k}=\sum\limits_{i=0}^{k}C_{n}^{i}i!S_2(k,i)\)。\(S_2\)表示第二类斯特林数。

\[原式=\displaystyle\sum_{i=0}^{n}C_{n}^{i}\sum_{j=0}^{k}C_{i}^{j}\cdot j!S_2(k,j)\\
=\sum_{i=0}^{n}C_n^i\sum_{j=0}^k C_i^jj!S_2(k,j)
\]

因为\(k\)的规模远小于\(n\)的规模，所以我们交换一下求和符号，在最外层枚举到\(k\)：

\[原式=\displaystyle\sum_{j=0}^{k}S_2(k,j)j!\sum_{i=j}^{n} C_n^iC_i^j。
\]

这里有一个结论：\(C_n^iC_i^j=C_n^jC_{n-i}^{j-i}\)

它的组合数意义是：先从n个数中取i个，再在那i个数中取j个；与先取j个，再在剩下的数中取i-j个。这两个方案是等价的。

这样，我们就得到了一个\(O(k)的式子:\displaystyle\sum_{j=0}^{k}S_2(k,j)j!C_n^j\sum_{i=j}^{n} C_{n-j}^{i-j}\)。

计算\(C_n^j\)的时候可以计算\(n!*(n-1)!*...*(n-j+1)!再除以j!\)。

然后\(\displaystyle\sum_{i=j}^{n} C_{n-j}^{i-j}=\sum_{d=0}^{n-j}C_{n-j}^d=2^{n-j}\)。于是这个问题就解决了。

代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

ll n,k;

ll fac[5005],inv[5005],suf[5005];

ll s[5005][5005];

const ll mod=1e9+7;

ll ksm(ll t,ll x) {

	ll ans=1;

	for(;x;x>>=1,t=t*t%mod)

		if(x&1) ans=ans*t%mod;

	return ans;

}

ll C(int n,int m) {return fac[n]*ksm(fac[m]*fac[n-m]%mod,mod-2)%mod;}

ll cal(int n,int k) {

	if(!k) return 1;

	return suf[k-1]*inv[k]%mod;

}

int main() {

	n=Get(),k=Get();

	s[0][0]=1;

	for(int i=1;i<=k;i++)

		for(int j=1;j<=i;j++)

			s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%mod;

	fac[0]=1;

	for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;

	inv[k]=ksm(fac[k],mod-2);

	for(int i=k-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

	suf[0]=n;

	for(int i=1;i<=k;i++) suf[i]=suf[i-1]*(n-i)%mod;

	ll ans=0;

	int lim=min(n,k);

	for(int i=0;i<=lim;i++) {

		(ans+=s[k][i]*fac[i]%mod*cal(n,i)%mod*ksm(2,n-i)%mod)%=mod;

	}

	cout<<ans;

	return 0;

}

巴特西

CF 932E Team Work

最新文章

热门文章