企业官网建设流程全解析

题目：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 N+1N+1行：第i + 1 i+1i+1行有一个整数R i R_iRi​，表示第i ii头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对10 8 10^8108取模的值。

输入输出样例 #1

输入 #1

4 5 1 2 8 2

输出 #1

3

说明/提示

对于100 % 100\%100%的数据，1 ≤ N ≤ 2000 1 \le N \le 20001≤N≤2000，1 ≤ F ≤ 1000 1 \le F \le 10001≤F≤1000，1 ≤ R i ≤ 10 5 1 \le R_i \le 10^51≤Ri​≤105。

思路

状态表示：
f[i][j]表示从前i头奶牛中选且能力和%F的余数为j的方案数

每头奶牛有选和不选两种方案，所以是01背包

转移方程：
选i+不选i
f[i][j]=f[i-1][j]+f[i][?]

f[i][?]是指从前i-1头奶牛中选且?+v[i]后%F的余数为j，转化一下就是(?+v[i])%F=j，所以?=(j-v[i])%F

由于j-v[i]可能为负数，所以用个小技巧：(j-v[i]+F)%F

由于(j-v[i]+F)%F不一定单调，所以用二维比较方便

输出：
能力和为F的倍数，所以余数应该为0

代码（二维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=2000+10,M=1e3+10,MOD=1e8;longlongn,V,v[N],F;longlongf[N][M],ans;intmain(){scanf("%lld%lld",&n,&F);for(inti=1;i<=n;i++){scanf("%lld",&v[i]);v[i]%=F;}f[0][0]=1;for(inti=1;i<=n;i++)for(intj=0;j<F;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;}

结果