题目P2946 [USACO09MAR] Cow Frisbee Team S题目描述老唐最近迷上了飞盘约翰想和他一起玩于是打算从他家的N NN头奶牛中选出一支队伍。每只奶牛的能力为整数第i ii头奶牛的能力为R i R_iRi​。飞盘队的队员数量不能少于1 11、大于N NN。一支队伍的总能力就是所有队员能力的总和。约翰比较迷信他的幸运数字是F FF所以他要求队伍的总能力必须是F FF的倍数。请帮他算一下符合这个要求的队伍组合有多少由于这个数字很大只要输出答案对10 8 10^8108取模的值。输入格式第一行两个用空格分开的整数N NN和F FF。第二行到N 1 N1N1行第i 1 i1i1行有一个整数R i R_iRi​表示第i ii头奶牛的能力。输出格式第一行单个整数表示方案数对10 8 10^8108取模的值。输入输出样例 #1输入 #14 5 1 2 8 2输出 #13说明/提示对于100 % 100\%100%的数据1 ≤ N ≤ 2000 1 \le N \le 20001≤N≤20001 ≤ F ≤ 1000 1 \le F \le 10001≤F≤10001 ≤ R i ≤ 10 5 1 \le R_i \le 10^51≤Ri​≤105。思路状态表示f[i][j]表示从前i头奶牛中选且能力和%F的余数为j的方案数每头奶牛有选和不选两种方案所以是01背包转移方程选i不选if[i][j]f[i-1][j]f[i][?]f[i][?]是指从前i-1头奶牛中选且?v[i]后%F的余数为j转化一下就是(?v[i])%Fj所以?(j-v[i])%F由于j-v[i]可能为负数所以用个小技巧(j-v[i]F)%F由于(j-v[i]F)%F不一定单调所以用二维比较方便输出能力和为F的倍数所以余数应该为0代码二维数组#includebits/stdc.husingnamespacestd;constintN200010,M1e310,MOD1e8;longlongn,V,v[N],F;longlongf[N][M],ans;intmain(){scanf(%lld%lld,n,F);for(inti1;in;i){scanf(%lld,v[i]);v[i]%F;}f[0][0]1;for(inti1;in;i)for(intj0;jF;j)f[i][j](f[i-1][j]f[i-1][(j-v[i]F)%F]%MOD)%MOD;printf(%lld,f[n][0]-1);return0;}结果