Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <memory.h>
- const int MOD = 1000000007, N = 205, K = 10;
- int dp[N][N][5][3], C[K][K], con[5], get[5], fact = 1, n, k;
- inline void add(int &v1, int v2) {
- v1 += v2;
- if (v1 >= MOD)
- v1 -= MOD;
- }
- inline int mul(int v1, int v2) {
- long long res = v1;
- res *= v2;
- return (res % MOD);
- }
- int calc(int level, int operations, int cur, int type) {
- int &ans = dp[level][operations][cur][type];
- if (ans != -1)
- return ans;
- ans = 0;
- if (type == 0) {
- int bits = get[cur];
- for(int i = 0; (i <= bits) && (i <= operations); i++)
- add(ans, mul(calc(level - 1, operations - i, cur, 2), C[bits][i]));
- }
- if (type == 1) {
- if (level == 0) {
- if (operations == 0)
- return ans = 1;
- else
- return ans = 0;
- }
- int bits = get[cur];
- bits <<= 1;
- int cons = con[cur];
- for(int i = 0; (i <= cons) && (i <= operations); i++)
- for(int j = 0; (j <= (bits - 2 * i)) && (j <= (operations - i)); j++)
- add(ans, mul(calc(level, operations - i - j, cur, 0), mul(C[cons][i], C[bits - 2 * i][j])));
- }
- if (type == 2) {
- add(ans, calc(level, operations, cur, 1));
- if (cur == 0) {
- if (operations >= 1) {
- add(ans, mul(calc(level, operations - 1, 1, 1), 4));
- add(ans, mul(calc(level, operations - 1, 2, 1), 4));
- }
- if (operations >= 2) {
- add(ans, mul(calc(level, operations - 2, 4, 1), 2));
- add(ans, mul(calc(level, operations - 2, 2, 1), 4));
- add(ans, mul(calc(level, operations - 2, 3, 1), 8));
- if (operations == 2)
- add(ans, 2);
- }
- if (operations >= 3) {
- add(ans, mul(calc(level, operations - 3, 3, 1), 4));
- if (operations == 3)
- add(ans, 4);
- }
- if (operations == 4)
- add(ans, 1);
- }
- if (cur == 1) {
- if (operations >= 1) {
- add(ans, calc(level, operations - 1, 4, 1));
- add(ans, mul(calc(level, operations - 1, 2, 1),2));
- add(ans, mul(calc(level, operations - 1, 3, 1),2));
- }
- if (operations >= 2) {
- if (operations == 2)
- add(ans, 2);
- add(ans, mul(calc(level, operations - 2, 3, 1), 3));
- }
- if (operations == 3)
- add(ans, 1);
- }
- if (cur == 2) {
- if (operations >= 1) {
- add(ans, mul(calc(level, operations - 1, 3, 1), 2));
- if (operations == 1)
- add(ans, 1);
- }
- if (operations == 2)
- add(ans, 1);
- }
- if (cur == 3 && operations == 1)
- add(ans, 1);
- if (cur == 4) {
- if (operations >= 1) add(ans, mul(calc(level, operations - 1, 3, 1), 2));
- if (operations == 2)
- add(ans, 1);
- }
- }
- return ans;
- }
- int main() {
- get[0] = 4; con[0] = 4;
- get[1] = 3; con[1] = 2;
- get[2] = 2; con[2] = 1;
- get[3] = 1; con[3] = 0;
- get[4] = 2; con[4] = 0;
- for(int i = 0; i < K; i++) {
- C[i][0] = 1;
- for(int j = 1; j <= i; j++)
- add(C[i][j], C[i - 1][j]), add(C[i][j], C[i - 1][j - 1]);
- }
- memset(dp, -1, sizeof dp);
- scanf("%d %d", &n, &k);
- for(int i = 1; i <= k; i++) fact = mul(fact, i);
- printf("%d\n", mul(fact,calc(n, k, 0, 2)));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement