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
",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;
}