Hdu 5464 Clarke and problem (dp)

题目链接：

　　BestCoder Round #56 (div.1) 1002  Clarke and problem

题目描述：

　　给出n个数，从中挑出任意个数，挑出的数字的和求余p等于零，问有多少种挑选情况？

解题思路：

　　dp[i][j]代表前i个数加起来余数为j的取数方案。注意一下ai有可能小于0，这个题目就基本可以秒A了。

　　简单dp，不知道为什么第一眼看完题目马上想到HASH余数(思路都错)，果然是dp太弱。这场BC还好错过没打，要不真是一场送分跌名的噩梦。

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
const int mod = 1000000007;
typedef long long LL;
LL dp[2][maxn];

int main ()
{
    LL T, n, p, num;
    scanf ("%lld", &T);
    while (T --)
    {
        scanf ("%lld %lld", &n, &p);
        memset (dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i=0; i<n; i++)
        {
            scanf ("%lld", &num);
            num = (num % p + p) % p;
            for (int j=0; j<p; j++)
                dp[(i+1)&1][(j+num)%p] = (dp[i&1][(j+num)%p] + dp[i&1][j])%mod;
        }
        printf ("%lld
", dp[n&1][0]);
    }
    return 0;
}