从序列A中选出一些数,使得总和为m的倍数,求有几种选法?
f[i][j] ,考虑前i个,总和的余数为j 时的 方案数 (a[i]%m)
f[i] [j ]+= f[i-1][j] +f[i-1][ j-a[i] ]
#include <bits/stdc++.h> using namespace std ; const int N=2002,mod=1e8; int n,m,a[N],f[N][N]; signed main(){ int i,j,H,t=0; cin>>n>>H; for(i=1;i<=n;i++) cin>>a[i],a[i]%=H; for(i=1;i<=n;i++) f[i][a[i]]=1; for(i=1;i<=n;i++) for(j=0;j<H;j++){ f[i][j]+=f[i-1][j]+f[i-1][(j-a[i]+H)%H]; f[i][j]%=mod; } cout<<f[n][0]; }
标签:Frisbee,Cow,P2946,USACO09MAR,int,Team From: https://www.cnblogs.com/towboa/p/17181436.html