背包)"/>
P2946 [USACO09MAR] Cow Frisbee Team S(01背包)
[USACO09MAR] Cow Frisbee Team S
题目描述
老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的 N N N 头奶牛中选出一支队伍。
每只奶牛的能力为整数,第 i i i 头奶牛的能力为 R i R_i Ri 。飞盘队的队员数量不能少于 1 1 1、大于 N N N。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信,他的幸运数字是 F F F ,所以他要求队伍的总能力必须是 F F F 的倍数。请帮他
算一下,符合这个要求的队伍组合有多少?由于这个数字很大,只要输出答案对 1 0 8 10^8 108 取模的值。
输入格式
第一行:两个用空格分开的整数: N N N 和 F F F。
第二行到 N + 1 N+1 N+1 行:第 i + 1 i+1 i+1 行有一个整数 R i R_i Ri ,表示第 i i i 头奶牛的能力。
输出格式
第一行:单个整数,表示方案数对 1 0 8 10^8 108 取模的值。
样例 #1
样例输入 #1
4 5
1
2
8
2
样例输出 #1
3
提示
数据范围与约定
- 对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2000 1 \le N \le 2000 1≤N≤2000, 1 ≤ F ≤ 1000 1 \le F \le 1000 1≤F≤1000 , 1 ≤ R i ≤ 1 0 5 1 \le R_i \le 10^5 1≤Ri≤105
解析
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=2010,mod=1e8;
int n,f,a[N],dp[N][N];
void solve(){scanf("%d%d",&n,&f);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]%=f;dp[i][a[i]]=1;}for(int i=1;i<=n;i++){for(int j=0;j<f;j++){dp[i][j]+=dp[i-1][j]+dp[i-1][(j-a[i]+f)%f];dp[i][j]%=mod;}}cout<<dp[n][0];
}
signed main(){int t=1;
// scanf("%lld",&t);while(t--) solve();return 0;
}
更多推荐
P2946 [USACO09MAR] Cow Frisbee Team S(01背包)
发布评论