题目描述
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 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; }
