SFZOJ 1008
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 N 头奶牛中选出一支队伍。
每只奶牛的能力为整数，第 i 头奶牛的能力为Ri 。飞盘队的队员数量不能少于 1、大于N。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信，他的幸运数字是 F，所以他要求队伍的总能力必须是 F的倍数。请帮他
算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 10^8取模的值。
刷表法
#include <bits/stdc++.h>
#define MOD 100000000
using namespace std;
int n, a[2005], k, f[2005][1000];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
f[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < k; j++) {
f[i + 1][(j + a[i + 1]) % k] += f[i][j];
f[i + 1][(j + a[i + 1]) % k] %= MOD;
f[i + 1][j] += f[i][j];
f[i + 1][j] %= MOD;
}
}
printf("%d\n", f[n][0] - 1);
return 0;
}
/*
f[][2 + 3] (2+3)%3 = 2
f[][5 + 3] (5+3)%3 = 2
4 5
1 2 8 2
0 1 2 3 4 5 6 7 8 9 10
0 1
1 1 1
2 1 1 1
3 1
4 1
*/填表法
#include <bits/stdc++.h>
#define MOD 100000000
using namespace std;
int n, a[2005], k, f[2005][1000];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
f[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
(f[i + 1][(j + a[i + 1]) % k] += f[i][j]) %= MOD;
(f[i + 1][j] += f[i][j]) %= MOD;
}
}
printf("%d\n", f[n][0] - 1);
return 0;
}
/*
f[][2 + 3] (2+3)%3 = 2
f[][5 + 3] (5+3)%3 = 2
4 5
1 2 8 2
0 1 2 3 4 5 6 7 8 9 10
0 1
1 1 1
2 1 1 1
3 1
4 1
*/