fork download
  1. /*
  2. ID: untamed
  3. PROG: COINCHANGE2
  4. LANG: C++
  5. */
  6.  
  7. #include<cstdio>
  8. #include<iostream>
  9. #include<algorithm>
  10. #include<string>
  11. #include<cstring>
  12. #include<vector>
  13. #include<stack>
  14. #include<queue>
  15. #include<deque>
  16. #include<map>
  17. #include<set>
  18. #include<limits>
  19. #include<climits>
  20. #include<cmath>
  21. #include<functional>
  22. #include<ctime>
  23. #include<cstdlib>
  24. #include<fstream>
  25. #include<typeinfo>
  26.  
  27. const int ONE = 1<<10;
  28. const int TWO = 1<<11;
  29. const int FOUR = 1<<12;
  30. const int EIGHT = 1<<13;
  31. const int SIXTEEN = 1<<14;
  32. const int THIRTY = 1<<15;
  33. const int SIXTY = 1<<16;
  34. const int ONE_HUNDRED = 1<<17;
  35. const int TWO_HUNDRED = 1<<18;
  36. const int FIVE_HUNDRED = 1<<19;
  37. const int MILLION = 1<<20;
  38.  
  39. using namespace std;
  40.  
  41. typedef long long int ll;
  42. typedef short int i16;
  43. typedef unsigned long long int u64;
  44. typedef unsigned int u32;
  45. typedef unsigned short int u16;
  46. typedef unsigned char u8;
  47.  
  48. const int MOD = 100000007;
  49.  
  50. int n,k;
  51. int a[128];
  52.  
  53. int state[128][SIXTEEN];
  54.  
  55. void input()
  56. {
  57. scanf("%d %d", &n, &k);
  58. for(int i=1;i<=n;i++)
  59. {
  60. scanf("%d", &a[i]);
  61. }
  62. }
  63.  
  64. void solve()
  65. {
  66. memset(state,0,sizeof(state));
  67. int i,j;
  68. for(i=1;i<=n;i++)
  69. {
  70. state[i][0]=1;
  71. for(j=1;j<=k;j++)
  72. {
  73. state[i][j]=(state[i][j-a[i]]+state[i-1][j])%MOD;
  74. }
  75. }
  76. printf("%d\n", state[n][k]);
  77. }
  78.  
  79. int main()
  80. {
  81. int i,t;
  82. scanf("%d", &t);
  83. for(i=1;i<=t;i++)
  84. {
  85. input();
  86. printf("Case %d: ", i);
  87. solve();
  88. }
  89. return 0;
  90. }
  91.  
Success #stdin #stdout 0s 11336KB
stdin
Standard input is empty
stdout
Standard output is empty