hdu 5464 dp

类似背包的简单dp，dp[i][j]表示枚举前i个数字的组合mod p的值为j的方法数，要求的答案即为dp[n][0]。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int MOD = 1000000007;
 7 const int N = 1000;
 8 int a[N];
 9 int b[N];
10 
11 int main ()
12 {
13     int t;
14     scanf("%d", &t);
15     while ( t-- )
16     {
17         int n, p;
18         scanf("%d%d", &n, &p);
19         memset( a, 0, sizeof(a) );
20         a[0] = 1;
21         for ( int i = 0; i < n; i++ )
22         {
23             int tmp;
24             scanf("%d", &tmp);
25             memset( b, 0, sizeof(b) );
26             for ( int i = 0; i < p; i++ )
27             {
28                 int c = ( ( i + tmp ) % p + p ) % p;
29                 b[c] += a[i];
30                 if ( b[c] >= MOD ) b[c] -= MOD;
31             }
32             for ( int i = 0; i < p; i++ )
33             {
34                 a[i] += b[i];
35                 if ( a[i] >= MOD ) a[i] -= MOD;
36             }
37         }
38         printf("%d
", a[0]);
39     }
40     return 0;
41 }