Clarke and problem

? ?Accepts: 169 ? ?Submissions: 372 ?Time Limit: 2000/1000 MS (Java/Others) ? ?Memory Limit: 65536/65536 K (Java/Others) 問題描述 克拉克是一名人格分裂患者。某一天，克拉克分裂成了一個學生，在做題。 突然一道難題難到了克拉克，這道題是這樣的： 給你nn個數，要求選一些數（可以不選），把它們加起來，使得和恰好是pp的倍數（00也是pp的倍數），求方案數。 對于nn很小的時候，克拉克是能輕易找到的。然而對于nn很大的時候，克拉克沒有辦法了，所以來求助于你。 輸入描述 第一行一個整數T(1 \le T \le 10)T(1≤T≤10)，表示數據的組數。 每組數據第一行是兩個正整數n, p(1 \le n, p \le 1000)n,p(1≤n,p≤1000)。 接下來的一行有nn個整數a_i(|a_i| \le 10^9)a?i??(∣a?i??∣≤10?9??)，表示第ii個數。 輸出描述 對于每組數據，輸出一個整數，表示問題的方案數，由于答案很大，所以求出對10^9+710?9??+7的答案即可。 輸入樣例 1 2 3 1 2 輸出樣例 2 Hint 有兩種方案：什么也不選；全都選。



果然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=0?p?1??d(i?1,(j?a[i])?mod?p)，很多人沒1a是因為沒注意|a_i| \le 10^9∣a?i??∣≤10?9??
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 26 using namespace std; 27 #define For(i, n) for (int i=0;i<int(n);++i) 28 typedef long long LL; 29 typedef double DB; 30 const int inf = 0x3f3f3f3f; 31 const int N = 1E3+5; 32 const int MOD = 1E9+7; 33 LL a[N],dp[N][N]; 34 int n,p; 35 int 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 } View Code

?

?

轉載于:https://www.cnblogs.com/111qqz/p/4828338.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的bestcoder #56 div 2 B Clarke and problem(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。