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 泛型背包]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。