[jzoj]4271. 【NOIP2015模拟10.27】魔法阵（37种转移的dp）

  • 题意不说

  • 应该这辈子都不会忘记了...

  • 这是我人生中做的最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
", ans);
}

int main() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	
	Init();
	
	GetMul();
	
	FindTheAns();

	SolveAns();
	
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Pro-king/p/9391851.html