bestcoder #56 div 2 B Clarke and problem(dp)
果然dp還是弱項啊啊啊啊．． 不過比最開始的完全無從下手強了不少應該．．．
至少dp狀態表示相對了．．．．轉移方程沒想出來嗚嗚嗚
官方題解：设d(i, j)d(i,j)表示前ii个数，模pp为jj的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+sum_{j=0}^{p-1} d(i-1, (j-a[i]) mod p)d(0,0)=1,d(i,j)=d(i−1,j)+∑j=0p−1d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| le 10^9∣ai∣≤109
1/*************************************************************************
2 > File Name: code/bc/#56/1002.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月22日 星期二 10时47分20秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N = 1E3+5;
32const int MOD = 1E9+7;
33LL a[N],dp[N][N];
34int n,p;
35int main()
36{
37 #ifndef ONLINE_JUDGE
38 freopen("in.txt","r",stdin);
39 #endif
40 int T;
41 cin>>T;
42 while (T--)
43 {
44 scanf("%d %d",&n,&p);
45 for ( int i = 1 ; i <= n ; i++) scanf("%lld",&a[i]);
46 ms(dp,0);
47 dp[0][0] = 1;
48
49 for ( int i = 1 ; i <= n ; i++)
50 {
51 for ( int j = 0 ; j < p ; j ++)
52 dp[i][j] = dp[i-1][j];
53
54
55 for ( int j = 0 ; j < p ; j++)
56 dp[i][((j+a[i])%p+p)%p] +=dp[i-1][j];
57 for ( int j = 0 ; j < p ; j++)
58 dp[i][j]%=MOD;
59 }
60 printf("%lld\n",dp[n][0]);
61 }
62
63
64 #ifndef ONLINE_JUDGE
65 fclose(stdin);
66 #endif
67 return 0;
68}