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
/*************************************************************************
> File Name: code/bc/#56/1002.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月22日 星期二 10时47分20秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define ms(a,x) memset(a,x,sizeof(a))
18#define lr dying111qqz
19using namespace std;
20#define For(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef double DB;
23const int inf = 0x3f3f3f3f;
24const int N = 1E3+5;
25const int MOD = 1E9+7;
26LL a[N],dp[N][N];
27int n,p;
28int main()
29{
30 #ifndef ONLINE_JUDGE
31 freopen("in.txt","r",stdin);
32 #endif
33 int T;
34 cin>>T;
35 while (T--)
36 {
37 scanf("%d %d",&n,&p);
38 for ( int i = 1 ; i <= n ; i++) scanf("%lld",&a[i]);
39 ms(dp,0);
40 dp[0][0] = 1;
1 for ( int i = 1 ; i <= n ; i++)
2 {
3 for ( int j = 0 ; j < p ; j ++)
4 dp[i][j] = dp[i-1][j];
1 for ( int j = 0 ; j < p ; j++)
2 dp[i][((j+a[i])%p+p)%p] +=dp[i-1][j];
3 for ( int j = 0 ; j < p ; j++)
4 dp[i][j]%=MOD;
5 }
6 printf("%lld\n",dp[n][0]);
7 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}