题目链接：http://begin.lydsy.com/JudgeOnline/problem.php?id=1375
题意：
给你n个数，你可以从中选任意多个，但不能不选。问你所选数字之和为f的倍数的方案数。
题解：
表示状态：
dp[i][j] = num of ways
i：考虑到第i个数（还没选）
j：之前所选数之和 MOD f == j
找出答案：
ans = dp[n][0] - 1
不选也是一种方案，但题目种要求不能不选，所以-1。
如何转移：
选或不选第i个数。
dp[i+1][j] += dp[i][j] （不选）
dp[i+1][(j+r[i])%f] += dp[i][j] （选）
边界条件：
dp[0][0] = 1 （什么都不选也是一种方案）
others = 0
AC Code:
// state expression:
// dp[i][j] = num of ways
// i: considering ith cow
// j: sum MOD f == j
//
// find the answer:
// dp[n][0]
//
// transferring:
// now: dp[i][j]
// dp[i+1][j] += dp[i][j]
// dp[i+1][(j+r[i])%f] += dp[i][j]
//
// boundary:
// dp[0][0] = 1
// others = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005
#define MAX_F 1005
#define MOD 100000000 using namespace std; int n,f;
int r[MAX_N];
int dp[MAX_N][MAX_F]; void read()
{
cin>>n>>f;
for(int i=;i<n;i++)
{
cin>>r[i];
}
} void solve()
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<n;i++)
{
for(int j=;j<f;j++)
{
dp[i+][j]=(dp[i+][j]+dp[i][j])%MOD;
dp[i+][(j+r[i])%f]=(dp[i+][(j+r[i])%f]+dp[i][j])%MOD;
}
}
} void print()
{
cout<<((dp[n][]-)%MOD+MOD)%MOD<<endl;
} int main()
{
read();
solve();
print();
}