[CSAcademy]Sum of Powers

题目大意：

给定\(n,m,k(n,m,k\le4096)\)。一个无序可重集\(A\)为合法的，当且仅当\(|A|=m\)且\(\sum A_i=n\)。定义一个集合的贡献为\(\sum A_i^k\)，求所有满足条件的集合的贡献之和。

思路：

\(f[i][j]\)表示将\(j\)个数之和为\(i\)的方案数，有如下两种转移：

\(f[i][j]+=f[i-1][j-1]\)，表示新加入一个元素\(1\)；
\(f[i][j]+=f[i-j][j]\)，表示集合内每个元素\(+1\)。

可以证明这样就不重复、不遗漏地包含了所有的集合。

由于每个元素的贡献独立，最后枚举每种元素及其出现次数并计算贡献即可。

时间复杂度\(\mathcal O(nm)\)。

源代码：

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=4097,mod=1e9+7;

int f[N][N];

inline int power(int a,int k) {

	int ret=1;

	for(;k;k>>=1) {

		if(k&1) ret=1ll*ret*a%mod;

		a=1ll*a*a%mod;

	}

	return ret;

}

int main() {

	const int n=getint(),m=getint(),k=getint();

	f[0][0]=1;

	for(register int i=1;i<=n;i++) {

		for(register int j=1;j<=m&&j<=i;j++) {

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

		}

	}

	int ans=0;

	for(register int i=1;i<=n-m+1;i++) {

		const int pwr=power(i,k);

		for(register int j=1;j<=m&&i*j<=n;j++) {

			(ans+=1ll*pwr*f[n-i*j][m-j]%mod)%=mod;

		}

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

[CSAcademy]Sum of Powers

[CSAcademy]Sum of Powers

题目大意：

思路：

源代码：

最新文章

热门文章