P2946 [USACO09MAR] Cow Frisbee Team S（01背包）

背包）"/>

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;
}