1693: 【作】【基础】奶牛沙盘队
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：1
题目描述
Farmer Han开始玩飞盘之后，YDS也打算让奶牛们享受飞盘的乐趣．他要组建一只奶牛飞盘队．他的N(1≤N≤2000)只奶牛，每只奶牛有一个飞盘水准指数Ri(1≤Ri≤100000)．YDS要选出1只或多于1只奶牛来参加他的飞盘队．由于YDS的幸运数字是F(1≤F≤1000)，他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数．
帮YDS算算一共有多少种组队方式．组队方式数模10^8取余的结果．
输入
第1行输入N和F，之后N行输入Ri
输出
组队方式数模10^8取余的结果
样例输入 复制
4 5
1
2
8
2
样例输出 复制
3提示
这就是一个类似于背包的问题。对于每头牛都有取和不取两种选择。
用表示在前头牛中选择，所选数之和结果为的方案数。（以下用“和为”表示“和结果为”。）
- 若不取，则应在前头牛中取来若干和为的数，方案数即为。
- 若取，则应在前头牛中取来若干和为的数，这样加上后，和才能等于，即。
所以。
这里还有一个关于取模的问题要解决。我们要用到的只是的余数，所以输入时就先将对取模。
还有就是可能为负数，这时就得写成(j-r[i]+F)%F，就为正了。
初始化为。
#include<bits/stdc++.h>
const int p=1e8;//定义常数
const int N=2000+10;
const int F=1000+10;
using namespace std;
int n,f,r[N],s[N][F];
long long h[N][F];
int main()
{
int i,j;
cin>>n>>f;
for(i=1;i<=n;i++)
{
cin>>r[i];
r[i]%=f;//提前取模
}
for(i=1;i<=n;i++) h[i][r[i]]=1;//初始化
for(i=1;i<=n;i++)
for(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;
}