CodeChef Cards, bags and coins [DP 泛型背包]

https://www.codechef.com/problems/ANUCBC

n个数字，选出其一个子集。
求有多少子集满足其中数字之和是m的倍数。n $\le$ 100000，m $\le$ 100，最
多90组数据

---

 

傻逼题模数取什么1e9+9毁我一节课该死煞笔提

[15:13:47]刚刚心塞了一会儿出去跑了几步好点了，然后发现好像是生物老师在艺术楼走廊上给人讲题(今天好像有学校给成绩好的单独上课之类的活动，好多同学都来了艺术楼的一个教室了和机房隔一个拐角........)

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N=1e5+5,M=105,INF=1e9+5,P=1e9+9; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int n,Q,m,a[N],d[M]; ll f[M][M],g[M]; ll inv[N]; inline void mod(ll &x){if(x>=P) x-=P;} void dp(){memset(f,0,sizeof(f));for(int i=0;i<m;i++){for(int j=0;j<m;j++) g[j]=0;ll c=1;mod(g[0]+=1);for(int j=1;j<=d[i];j++){c=c*(d[i]-j+1)%P*inv[j]%P;mod(g[i*j%m]+=c);}if(i==0) {f[0][0]=g[0];continue;}for(int j=0;j<m;j++)for(int k=0;k<m;k++) if(g[k]) mod(f[i][j]+=f[i-1][(j-k+m)%m]*g[k]%P);}printf("%d\n",f[m-1][0]); } int main(){freopen("in","r",stdin);inv[1]=1;for(int i=2;i<=100000;i++) inv[i]=(P-P/i)*inv[P%i]%P;int T=read();while(T--){n=read();Q=read();for(int i=1;i<=n;i++) a[i]=read();while(Q--){m=read();for(int i=0;i<m;i++) d[i]=0;for(int i=1;i<=n;i++) d[(a[i]%m+m)%m]++;dp();}}return 0; }

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的CodeChef Cards, bags and coins [DP 泛型背包]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。