取数字（dp优化）

给定n个整数\(a_i\)，你需要从中选取若干个数，使得它们的和是m的倍数。问有多少种方案。有多个询问，每次询问一个的m对应的答案。

\(1\le n\le 200000,1\le m\le 100,1\le q\le 30,-10^9\le a_i\le 10^9\)。

首先有一个暴力dp：\(f[i][j]\)表示选到第i个数，和mod m是j的方案数。但是显然，这个dp是\(O(nm)\)的，然后就tle了。

换一个思路dp？由于我们只需要一个数模m的值，可以先把所有数模m放到桶里，用\(f[i][j]\)表示选到第i个桶，余数和为j的方案数。那么，枚举这一个桶放了多少数k（rh奇怪的dp方法），\(f[i][j+ki]+=f[i-1][j]*\binom{b[i]}{k}\)。

这个dp是\(O(nm^2)\)的，能过50%。先把代码放上来：

#include 
    
     #include 
     
      using namespace std;typedef long long LL;const LL maxn=4e5+5, maxm=105, mod=1e9+7;LL n, q, m, a[maxn], b[maxm], f[maxm][maxm];LL fac[maxn], inv[maxn];LL C(LL x, LL y){ return fac[x]*inv[y]%mod*inv[x-y]%mod; }LL fpow(LL a, LL x){    LL ans=1, base=a;    for (; x; x>>=1, base*=base, base%=mod)        if (x&1) ans*=base, ans%=mod;    return ans;}int main(){    scanf("%lld%lld", &n, &q);     fac[0]=1; inv[0]=1;    for (LL i=1; i
     
    

我们在\((f[i][(j*i+w)\%m]+=f[i-1][w]*C(b[i], j))\%=mod;\)这行里可以发现：虽然j枚举到了b[i]，但是\((j*i+w)\)模了m。因此，只要枚举\(j=[0,m-1]\)就行了！

所以说：

• dp要多考虑几种方法突破。
• dp方程里如果带模数，有时是可以优化的。
• 只要不把求状态的顺序颠倒，可以交换dp中两个循环的位置

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long LL;const LL maxn=4e5+5, maxm=105, mod=1e9+7;LL n, q, m, a[maxn], b[maxm], f[maxm][maxm];LL fac[maxn], inv[maxn], pre[maxn];inline int min(LL x, LL y){ return x
        
         >=1, base*=base, base%=mod)        if (x&1) ans*=base, ans%=mod;    return ans;}int getint(){    char c; int flag=1, re=0;    for (c=getchar(); !isdigit(c); c=getchar())        if (c=='-') flag=-1;    for (re=c-48; c=getchar(), isdigit(c); re=re*10+c-48);    return re*flag;}int main(){    scanf("%lld%lld", &n, &q);     fac[0]=1; inv[0]=1;    for (LL i=1; i