题意不说
应该这辈子都不会忘记了...
这是我人生中做的最SB的一道DP题.
真的打的我心态崩了。。。。
可是竟然被我调出来了。。。。。
也是没谁了...
我们设\(F[i][j][S]\)表示到第\(i\)层，然后放了\(j\)个三角形，四个方向是否可以继续拓展的状态为\(S\).
然后分十五种情况进行转移.
每种转移里面再分类讨论。
然后数了数，总共有37种转移方式...
于是就是7k的代码....
#include <iostream>
#include <cstring>
#include <cstdio>
#define F(i, a, b) for (int i = a; i <= b; i++)
#define add(a, b) ((a) = (a + b) % Mo)
#define Mo 1000000007
using namespace std;
int n, k, F[210][410][16], D[15][15], E[15][15];
void Init() {
scanf("%d %d", &n, &k);
F[0][0][0] = 1;
F[0][1][1] = 1;
F[0][1][2] = 1;
F[0][1][4] = 1;
F[0][1][8] = 1;
F[0][1][0] = 4;
F[0][2][3] = 1;
F[0][2][6] = 1;
F[0][2][12] = 1;
F[0][2][9] = 1;
F[0][2][1] = 2;
F[0][2][2] = 2;
F[0][2][4] = 2;
F[0][2][8] = 2;
F[0][2][5] = 1;
F[0][2][10] = 1;
F[0][2][0] = 2;
F[0][3][7] = 1;
F[0][3][11] = 1;
F[0][3][13] = 1;
F[0][3][14] = 1;
F[0][3][3] = 1;
F[0][3][6] = 1;
F[0][3][12] = 1;
F[0][3][9] = 1;
F[0][4][15] = 1;
}
void GetMul() {
D[0][0] = 1;
F(i, 1, 14)
F(j, 1, 14)
D[i][j] = (D[i - 1][j] + D[i - 1][j - 1]) % Mo;
E[0][0] = 1;
F(i, 0, 13)
F(j, 0, 13)
E[i][j] = D[i + 1][j + 1];
}
void Doit0(int i, int j, int S, int T) {
if (F[i][j][S] == 0) return;
F(p, 0, 12) {
int up = min(p >> 1, 4);
F(q, 0, up)
add(F[i + 1][j + p - q][T], 1LL * F[i][j][S] * E[4][q] * E[12 - q * 2][p - 2 * q]);
}
}
void Doit1(int i, int j, int S, int T) {
if (F[i][j][S] == 0) return;
F(p, 0, 9) {
int up = min(p >> 1, 2);
F(q, 0, up)
add(F[i + 1][j + p - q][T], 1LL * F[i][j][S] * E[2][q] * E[9 - q * 2][p - q * 2]);
}
}
void Doit2(int i, int j, int S, int T, int S1, int S2) {
if (F[i][j][S] == 0) return;
// Not Add S1 or S2
F(p, 0, 9) {
int up = min(p >> 1, 2);
F(q, 0, up) {
add(F[i + 1][j + p - q][S1], 1LL * F[i][j][S] * E[2][q] * E[9 - q * 2][p - q * 2]);
add(F[i + 1][j + p - q][S2], 1LL * F[i][j][S] * E[2][q] * E[9 - q * 2][p - q * 2]);
}
}
// Add both
int yes = (T % 3 == 0);
F(p, 0, 6)
F(q, 0, min(p >> 1, yes))
add(F[i + 1][j + p - q][T], 1LL * F[i][j][S] * E[6 - q * 2][p - q * 2]);
if (yes) {
F(p, 0, 6)
F(q, 0, min(p >> 1, 1))
add(F[i + 1][j + p - q - 1][0], 1LL * F[i][j][S] * E[6 - q * 2][p - q * 2]);
}
}
void Doit3(int i, int j, int S, int T, int S1, int S2, int S3) {
if (F[i][j][S] == 0) return;
// Only Add one
F(p, 0, 9)
F(q, 0, min(p >> 1, 2)) {
int t = q * 2;
add(F[i + 1][j + p - q][S1], 1LL * F[i][j][S] * E[2][q] * E[9 - t][p - t]);
add(F[i + 1][j + p - q][S2], 1LL * F[i][j][S] * E[2][q] * E[9 - t][p - t]);
add(F[i + 1][j + p - q][S3], 1LL * F[i][j][S] * E[2][q] * E[9 - t][p - t]);
}
// Add two
F(p, 0, 6)
F(q, 0, min(p >> 1, 1)) {
int t = q * 2;
add(F[i + 1][j + p - q][S - S1], 1LL * F[i][j][S] * E[6 - t][p - t]);
add(F[i + 1][j + p - q][S - S3], 1LL * F[i][j][S] * E[6 - t][p - t]);
}
F(p, 0, 6)
F(q, 0, min(p >> 1, 0))
add(F[i + 1][j + p - q][S - S2], 1LL * F[i][j][S] * E[6 - q * 2][p - q *2]);
// Add all
F(p, 0, 3)
F(q, 0, min(p >> 1, 0))
add(F[i + 1][j + p - q][T], 1LL * F[i][j][S] * E[3 - q * 2][p - q * 2]);
// Only add one but the others are together
F(p, 0, 3)
F(q, 0, min(p >> 1, 0)) {
add(F[i + 1][j - 1 + p - q][S3], 1LL * F[i][j][S] * E[3 - q * 2][p - q * 2]);
add(F[i + 1][j - 1 + p - q][S1], 1LL * F[i][j][S] * E[3 - q * 2][p - q * 2]);
}
// Add no one but two are together
F(p, 0, 6)
F(q, 0, min(p >> 1, 1))
add(F[i + 1][j - 1 + p - q][T - S1 - S2 - S3], 2LL * F[i][j][S] * E[6 - q * 2][p - q * 2]);
}
void Doit4(int i, int j, int S, int S1, int S2, int S3, int S4) {
if (F[i][j][S] == 0) return;
// Not Add three
Doit1(i, j, S, S - 14);
Doit1(i, j, S, S - 13);
Doit1(i, j, S, S - 11);
Doit1(i, j, S, S - 7);
// Not Add two
F(p, 0, 6)
F(q, 0, min(p >> 1, 1)) {
int t = q * 2;
add(F[i + 1][j + p - q][S - S1 - S2], 1LL * F[i][j][S] * E[6 - t][p - t]);
add(F[i + 1][j + p - q][S - S2 - S3], 1LL * F[i][j][S] * E[6 - t][p - t]);
add(F[i + 1][j + p - q][S - S3 - S4], 1LL * F[i][j][S] * E[6 - t][p - t]);
add(F[i + 1][j + p - q][S - S4 - S1], 1LL * F[i][j][S] * E[6 - t][p - t]);
}
F(p, 0, 6)
F(q, 0, min(p >> 1, 0)) {
int t = q * 2;
add(F[i + 1][j + p - q][S - S1 - S3], 1LL * F[i][j][S] * E[6 - t][p - t]);
add(F[i + 1][j + p - q][S - S2 - S4], 1LL * F[i][j][S] * E[6 - t][p - t]);
}
// Not Add only one
F(p, 0, 3)
F(q, 0, min(p >> 1, 0)) {
int t = q * 2;
add(F[i + 1][j + p - q][S - S1], 1LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q][S - S2], 1LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q][S - S3], 1LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q][S - S4], 1LL * F[i][j][S] * E[3 - t][p - t]);
}
// Add all of them
add(F[i + 1][j][S], F[i][j][S]);
// Add both of them be together
add(F[i + 1][j - 1][S - S1 - S2], F[i][j][S]);
add(F[i + 1][j - 1][S - S2 - S3], F[i][j][S]);
add(F[i + 1][j - 1][S - S3 - S4], F[i][j][S]);
add(F[i + 1][j - 1][S - S4 - S1], F[i][j][S]);
// Add all of them be together // have 2 possible
add(F[i + 1][j - 2][0], F[i][j][S] * 2LL);
// Add both of them be together and have two possible
// possible 1
F(p, 0, 6)
F(q, 0, min(p >> 1, 1))
add(F[i + 1][j + p - q - 1][0], 4LL * F[i][j][S] * E[6 - q * 2][p - q * 2]);
// possible 2
F(p, 0, 3)
F(q, 0, min(p >> 1, 0)) {
int t = 2 * q;
add(F[i + 1][j + p - q - 1][S1], 2LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q - 1][S2], 2LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q - 1][S3], 2LL * F[i][j][S] * E[3 - t][p - t]);
add(F[i + 1][j + p - q - 1][S4], 2LL * F[i][j][S] * E[3 - t][p - t]);
}
}
void FindTheAns() {
F(i, 0, n - 1)
F(j, 0, k + 2) {
// S = 0;
F(p, 0, 15)
Doit0(i, j, p, 0);
// S = 1, 2, 4, 8
Doit1(i, j, 1, 1);
Doit1(i, j, 2, 2);
Doit1(i, j, 4, 4);
Doit1(i, j, 8, 8);
// S = 3, 6, 9, 12
Doit2(i, j, 3, 3, 1, 2);
Doit2(i, j, 6, 6, 2, 4);
Doit2(i, j, 12, 12, 4, 8);
Doit2(i, j, 9, 9, 1, 8);
// S = 5, 10
Doit2(i, j, 10, 10, 2, 8);
Doit2(i, j, 5, 5, 1, 4);
// S = 7, 11, 13, 14
Doit3(i, j, 7, 7, 1, 2, 4);
Doit3(i, j, 14, 14, 2, 4, 8);
Doit3(i, j, 13, 13, 4, 8, 1);
Doit3(i, j, 11, 11, 8, 1, 2);
// S = 15
Doit4(i, j, 15, 1, 2, 4, 8);
}
}
void SolveAns() {
int tot = 1, ans = 0;
F(i, 1, k)
tot = (1LL * tot * i) % Mo;
F(S, 0, 15)
add(ans, 1LL * F[n][k][S] * tot % Mo);
printf("%d\n", ans);
}
int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
Init();
GetMul();
FindTheAns();
SolveAns();
return 0;
}