SHARE
TWEET

Untitled

a guest Sep 25th, 2016 221 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:64000000")
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <list>
  7. #include <iterator>
  8. #include <cassert>
  9. #include <set>
  10. #include <queue>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <stack>
  14. #include <deque>
  15. #include <cmath>
  16. #include <memory.h>
  17. #include <cstdlib>
  18. #include <cstdio>
  19. #include <cctype>
  20. #include <algorithm>
  21. #include <utility>
  22. #include <time.h>
  23. #include <complex>
  24. using namespace std;
  25.  
  26. #define FOR(i, a, b) for(int i=(a);i<(b);i++)
  27. #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
  28. #define FILL(A,value) memset(A,value,sizeof(A))
  29.  
  30. #define ALL(V) V.begin(), V.end()
  31. #define SZ(V) (int)V.size()
  32. #define PB push_back
  33. #define MP make_pair
  34. #define Pi 3.14159265358979
  35. #define x0 ikjnrmthklmnt
  36. #define y0 lkrjhkltr
  37. #define y1 ewrgrg
  38.  
  39. typedef long long Int;
  40. typedef unsigned long long UInt;
  41. typedef vector<int> VI;
  42. typedef pair<int, int> PII;
  43. typedef pair<Int, Int> PLL;
  44. typedef pair<double, double> PDD;
  45. typedef complex<double> base;
  46.  
  47. const int INF = 1000000000;
  48. const int BASE = 1000000007;
  49. const int MAX = 107;
  50. const int MAXV = 100007;
  51. const int MAXE = 100000;
  52. const int ADD = 1000000;
  53. const int MOD = 1000000007;
  54. const int CNT = 800;
  55.  
  56. Int dp[107][37][17][17][4][4];
  57.  
  58. int main()
  59. {
  60.     //freopen("in.txt", "r", stdin);
  61.     //freopen("distance.in",  "r", stdin);
  62.     //freopen("distance.out", "w", stdout);
  63.     //freopen("out.txt" , "w" , stdout);
  64.  
  65.  
  66.     int n , m , k;
  67.     cin >> n >> m >> k;
  68.  
  69.     dp[0][0][0][0][0][0] = 1;
  70.     FOR(i,0,n)
  71.     {
  72.         int d = 0;
  73.         if (i < n - 1)
  74.             cin >> d;
  75.  
  76.         FOR(j,0,m)
  77.         {
  78.             FOR(c,0,k + 1)
  79.             {
  80.                 FOR(pr , 0 , k + 1)
  81.                 {
  82.                     FOR(sng ,0, 3)
  83.                     {
  84.                         FOR(ends,0,3)
  85.                         {
  86.                             Int val = dp[i][j][c][pr][sng][ends];
  87.  
  88.                             int opens = 2 * pr + sng;
  89.  
  90.                             dp[i + 1][(j + (opens) * d) % m][c][pr][sng][ends] += val;
  91.                             dp[i + 1][(j + (opens) * d) % m][c][pr][sng][ends] %= MOD;
  92.  
  93.                             if (ends < 2)
  94.                             {
  95.                                 dp[i + 1][(j + (opens + 1) * d) % m][c + 1][pr][sng + 1][ends + 1] += val;
  96.                                 dp[i + 1][(j + (opens + 1) * d) % m][c + 1][pr][sng + 1][ends + 1] %= MOD;
  97.                             }
  98.  
  99.                             dp[i + 1][(j + (opens + 2) * d) % m][c + 1][pr + 1][sng][ends] += val;
  100.                             dp[i + 1][(j + (opens + 2) * d) % m][c + 1][pr + 1][sng][ends] %= MOD;
  101.  
  102.                             dp[i + 1][(j + opens * d) % m][c + 1][pr][sng][ends] += val * (2 * pr + sng);
  103.                             dp[i + 1][(j + opens * d) % m][c + 1][pr][sng][ends] %= MOD;
  104.  
  105.                             if (ends < 2)
  106.                             {
  107.                                 if (pr > 0)
  108.                                 {
  109.                                     dp[i + 1][(j + (opens - 1) * d) % m][c + 1][pr - 1][sng + 1][ends + 1] += val * pr;
  110.                                     dp[i + 1][(j + (opens - 1) * d) % m][c + 1][pr - 1][sng + 1][ends + 1] %= MOD;
  111.                                 }
  112.                                 if (sng > 0 && pr == 0 && c + 1 == k)
  113.                                 {
  114.                                     dp[i + 1][j][c + 1][0][sng - 1][ends + 1] += val;
  115.                                     dp[i + 1][j][c + 1][0][sng - 1][ends + 1] %= MOD;
  116.                                 }
  117.                             }
  118.  
  119.                             if (pr == 0 && sng == 2 && c + 1 == k && ends == 2)
  120.                             {
  121.                                 dp[i + 1][j][c + 1][0][0][ends] += val;
  122.                                 dp[i + 1][j][c + 1][0][0][ends] %= MOD;
  123.                             }
  124.                             if (pr == 1 && sng == 0 && c + 1 == k && ends == 2)
  125.                             {
  126.                                 dp[i + 1][j][c + 1][0][0][ends] += val;
  127.                                 dp[i + 1][j][c + 1][0][0][ends] %= MOD;
  128.                             }
  129.  
  130.                             if (pr > 0 && sng > 0)
  131.                             {
  132.                                 dp[i + 1][(j + (opens - 2) * d) % m][c + 1][pr - 1][sng][ends] += val * pr * sng;
  133.                                 dp[i + 1][(j + (opens - 2) * d) % m][c + 1][pr - 1][sng][ends] %= MOD;
  134.                             }
  135.  
  136.                             if (pr > 1)
  137.                             {
  138.                                 dp[i + 1][(j + (opens - 2) * d) % m][c + 1][pr - 1][sng][ends] += val * pr * (pr - 1);
  139.                                 dp[i + 1][(j + (opens - 2) * d) % m][c + 1][pr - 1][sng][ends] %= MOD;
  140.                             }
  141.  
  142.                         }
  143.                     }
  144.                 }
  145.             }
  146.  
  147.         }
  148.  
  149.     }
  150.  
  151.     cout << dp[n][0][k][0][0][2] * 2 % MOD << endl;
  152.  
  153.     return 0;
  154. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top