[USACO09MAR]Cow Frisbee Team S
题目描述
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 \(N\) 头奶牛中选出一支队伍。
每只奶牛的能力为整数，第 \(i\) 头奶牛的能力为\(R_i\) 。飞盘队的队员数量不能少于 \(1\)、大于\(N\)。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信，他的幸运数字是 \(F\) ，所以他要求队伍的总能力必须是 \(F\) 的倍数。请帮他
算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 \(10^8\) 取模的值。
输入格式
第一行：两个用空格分开的整数：\(N\) 和 \(F\)。
第二行到 \(N+1\) 行：第 \(i+1\) 行有一个整数\(R_i\) ，表示第 \(i\) 头奶牛的能力。
输出格式
第一行：单个整数，表示方案数对 \(10^8\) 取模的值。
样例 #1
样例输入 #1
4 5
1
2
8
2
样例输出 #1
3
提示
数据范围与约定
- 对于 \(100\%\) 的数据，\(1 \le N \le 2000\)，\(1 \le F \le 1000\) ，\(1 \le R_i \le 10^5\) 。
解析
这就是一个类似于\(01\)背包的问题。对于每头牛都有取和不取两种选择。
用\(h[i][j]\)表示在前\(i\)头牛中选择，所选数之和\(mod \ F\)结果为\(j\)的方案数。（以下用“和为\(j\)”表示“和\(mod \ F\)结果为\(j\)”。）
- 若不取\(i\)，则应在前\(i-1\)头牛中取来若干和为\(j\)的数，方案数即为\(h[i-1][j]\)。
- 若取\(i\)，则应在前\(i-1\)头牛中取来若干和为\(j-r[i]\)的数，这样加上\(r[i]\)后，和才能等于\(j\)，即\(h[i-1][j-r[i]]\)。
所以$$h[i][j]=h[i][j]+h[i-1][j]+h[i-1][j-r[i]]$$
这里还有一个关于取模的问题要解决。我们要用到的只是\(r[i] \ mod \ F\)的余数，所以输入时就先将\(r[i]\)对\(F\)取模。
还有就是\(j-r[i]\)可能为负数，这时就得写成(j-r[i]+F)%F，就为正了。
初始化\(h[i][r[i]]\)为\(1\)。
AC代码
#include <bits/stdc++.h>
const int p=1e8;//定义常数
using namespace std;
int n,f,r[2010];
long long h[2010][1010];
int main()
{
cin >> n >> f;
for(int i=1;i<=n;i++)
{
cin >> r[i];
r[i]%=f;//提前取模
}
for(int i=1;i<=n;i++)
{
h[i][r[i]]=1;//初始化
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<f;j++)//余数范围：0到f-1
{
h[i][j]=((h[i][j]+h[i-1][j])%p+h[i-1][(j-r[i]+f)%f])%p;//每加一次就%p
}
}
cout<<h[n][0]<<endl;
return 0;
}