[CC-ANUCBC]Cards, bags and coins

题目大意：

给你\(n(n\le10^5)\)个数，\(q(q\le30)\)次询问，问从中选取若干个数使得这些数之和为\(m(m\le100)\)的方案数。

思路：

不难想到一个比较暴力的动态规划，用\(f[i][j]\)表示用了前\(i\)个数，和为\(j\)的方案数。时间复杂度\(\mathcal O(nmq)\)。

发现动态规划中我们只关心每个数在模\(m\)意义下的值，因此直接用\(n\)个数转移实在是太愚蠢了。

将这些数模\(m\)意义下相等的归为一类，最多有\(m\)类。直接用这\(m\)类数转移即可。

时间复杂度\(\mathcal O(qm^3)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

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

	return neg?-x:x;

}

typedef long long int64;

const int N=2e5+1,mod=1e9+9,M=100;

int a[N],f[M],g[M],fac[N],ifac[N],cnt[M],c[M];

void exgcd(const int &a,const int &b,int &x,int &y) {

	if(!b) {

		x=1,y=0;

		return;

	}

	exgcd(b,a%b,y,x);

	y-=a/b*x;

}

inline int inv(const int &x) {

	int ret,tmp;

	exgcd(x,mod,ret,tmp);

	return (ret%mod+mod)%mod;

}

inline int C(const int &n,const int &m) {

	return (int64)fac[n]*ifac[m]%mod*ifac[n-m]%mod;

}

int main() {

	for(register int i=fac[0]=1;i<N;i++) {

		fac[i]=(int64)fac[i-1]*i%mod;

	}

	ifac[N-1]=inv(fac[N-1]);

	for(register int i=N-1;i>=1;i--) {

		ifac[i-1]=(int64)ifac[i]*i%mod;

	}

	for(register int T=getint();T;T--) {

		const int n=getint(),q=getint();

		for(register int i=1;i<=n;i++) a[i]=getint();

		for(register int i=0;i<q;i++) {

			const int m=getint();

			std::fill(&cnt[0],&cnt[m],0);

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

				cnt[(a[i]%m+m)%m]++;

			}

			f[0]=1;

			std::fill(&f[1],&f[m],0);

			for(register int i=0;i<m;i++) {

				std::fill(&c[0],&c[m],0);

				for(register int j=0;j<=cnt[i];j++) {

					(c[(int64)i*j%m]+=C(cnt[i],j))%=mod;

				}

				std::copy(&f[0],&f[m],g);

				std::fill(&f[0],&f[m],0);

				for(register int j=0;j<m;j++) {

					for(register int k=0;k<m;k++) {

						(f[(j+k)%m]+=(int64)g[k]*c[j]%mod)%=mod;

					}

				}

			}

			printf("%d\n",f[0]);

		}

	}

	return 0;

}

巴特西

[CC-ANUCBC]Cards, bags and coins

[CC-ANUCBC]Cards, bags and coins

题目大意：

思路：

源代码：

最新文章

热门文章