洛谷 P2946 [USACO09MAR] Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 N 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 i 头奶牛的能力为 Ri​。飞盘队的队员数量不能少于 1、大于 N。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 F，所以他要求队伍的总能力必须是 F 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 108 取模的值。

输入格式

第一行：两个用空格分开的整数：N 和 F。

第二行到 N+1 行：第 i+1 行有一个整数 Ri​，表示第 i 头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对 108 取模的值。

输入输出样例

输入 #1复制

4 5 1 2 8 2

输出 #1复制

3

说明/提示

对于 100% 的数据，1≤N≤2000，1≤F≤1000，1≤Ri​≤105。

#include<bits/stdc++.h> using namespace std; const int N=2010,M=1010,MOD=1e8; int a[N]; int f[N][M]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<m;j++) { f[i][j]=(f[i-1][j]+f[i-1][((j-a[i]%m)%m+m)%m])%MOD; } } cout<<f[n][0]-1<<endl; return 0; }