Advertisement
Guest User

E

a guest
Aug 9th, 2013
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.95 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <memory.h>
  3.  
  4. const int MOD = 1000000007, N = 205, K = 10;
  5. int dp[N][N][5][3], C[K][K], con[5], get[5], fact = 1, n, k;
  6.  
  7. inline void add(int &v1, int v2) {
  8. v1 += v2;
  9. if (v1 >= MOD)
  10. v1 -= MOD;
  11. }
  12.  
  13. inline int mul(int v1, int v2) {
  14. long long res = v1;
  15. res *= v2;
  16. return (res % MOD);
  17. }
  18.  
  19. int calc(int level, int operations, int cur, int type) {
  20. int &ans = dp[level][operations][cur][type];
  21. if (ans != -1)
  22. return ans;
  23. ans = 0;
  24. if (type == 0) {
  25. int bits = get[cur];
  26. for(int i = 0; (i <= bits) && (i <= operations); i++)
  27. add(ans, mul(calc(level - 1, operations - i, cur, 2), C[bits][i]));
  28. }
  29. if (type == 1) {
  30. if (level == 0) {
  31. if (operations == 0)
  32. return ans = 1;
  33. else
  34. return ans = 0;
  35. }
  36. int bits = get[cur];
  37. bits <<= 1;
  38. int cons = con[cur];
  39. for(int i = 0; (i <= cons) && (i <= operations); i++)
  40. for(int j = 0; (j <= (bits - 2 * i)) && (j <= (operations - i)); j++)
  41. add(ans, mul(calc(level, operations - i - j, cur, 0), mul(C[cons][i], C[bits - 2 * i][j])));
  42. }
  43. if (type == 2) {
  44. add(ans, calc(level, operations, cur, 1));
  45. if (cur == 0) {
  46. if (operations >= 1) {
  47. add(ans, mul(calc(level, operations - 1, 1, 1), 4));
  48. add(ans, mul(calc(level, operations - 1, 2, 1), 4));
  49. }
  50. if (operations >= 2) {
  51. add(ans, mul(calc(level, operations - 2, 4, 1), 2));
  52. add(ans, mul(calc(level, operations - 2, 2, 1), 4));
  53. add(ans, mul(calc(level, operations - 2, 3, 1), 8));
  54. if (operations == 2)
  55. add(ans, 2);
  56. }
  57. if (operations >= 3) {
  58. add(ans, mul(calc(level, operations - 3, 3, 1), 4));
  59. if (operations == 3)
  60. add(ans, 4);
  61. }
  62. if (operations == 4)
  63. add(ans, 1);
  64. }
  65. if (cur == 1) {
  66. if (operations >= 1) {
  67. add(ans, calc(level, operations - 1, 4, 1));
  68. add(ans, mul(calc(level, operations - 1, 2, 1),2));
  69. add(ans, mul(calc(level, operations - 1, 3, 1),2));
  70. }
  71. if (operations >= 2) {
  72. if (operations == 2)
  73. add(ans, 2);
  74. add(ans, mul(calc(level, operations - 2, 3, 1), 3));
  75. }
  76. if (operations == 3)
  77. add(ans, 1);
  78. }
  79. if (cur == 2) {
  80. if (operations >= 1) {
  81. add(ans, mul(calc(level, operations - 1, 3, 1), 2));
  82. if (operations == 1)
  83. add(ans, 1);
  84. }
  85. if (operations == 2)
  86. add(ans, 1);
  87. }
  88. if (cur == 3 && operations == 1)
  89. add(ans, 1);
  90. if (cur == 4) {
  91. if (operations >= 1) add(ans, mul(calc(level, operations - 1, 3, 1), 2));
  92. if (operations == 2)
  93. add(ans, 1);
  94. }
  95. }
  96. return ans;
  97. }
  98.  
  99. int main() {
  100. get[0] = 4; con[0] = 4;
  101. get[1] = 3; con[1] = 2;
  102. get[2] = 2; con[2] = 1;
  103. get[3] = 1; con[3] = 0;
  104. get[4] = 2; con[4] = 0;
  105. for(int i = 0; i < K; i++) {
  106. C[i][0] = 1;
  107. for(int j = 1; j <= i; j++)
  108. add(C[i][j], C[i - 1][j]), add(C[i][j], C[i - 1][j - 1]);
  109. }
  110. memset(dp, -1, sizeof dp);
  111. scanf("%d %d", &n, &k);
  112. for(int i = 1; i <= k; i++) fact = mul(fact, i);
  113. printf("%d\n", mul(fact,calc(n, k, 0, 2)));
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement