Quad Tiling

題目連結：POJ 3420

題目大意

現有一個 4 × n 4\times n 4×n 的棋盤，問用 2 × 1 2\times 1 2×1 的多米諾骨牌将其完美覆寫的方法有多少種。

思路

這道題是狀态壓縮加矩陣乘法。

我們可以看到隻有 4 4 4 列，那我們可以考慮狀态壓縮。

然後我們想一想普通dp怎麼搞： f i , j f_{i,j} fi,j​ 為前 i − 1 i-1 i−1 列全部擺滿，然後第 i i i 列擺的情況是 j j j 有多少種方案。

然後就從每一個可以到的地方轉移過來。

然後你就會發現它其實就是一個 16 × 16 16\times 16 16×16 的矩陣。

然後這個矩陣乘 n n n 次，左上角的值就是答案。

這個矩陣是這樣的：

1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1
0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
           

至于這個矩陣怎麼得到，兩種方法，在代碼裡面講。

代碼

手推矩陣法

就是根據自己推理，一個一個求出來。

（或者就是打表）

反正我一開始就是這樣做的。

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

struct matrix {
	int n, m;
	ll a[21][21];
}a, b, re;
int n, m;
matrix operator *(matrix x, matrix y) {
	re.n = x.n;
	re.m = y.m;
	for (int i = 0; i < re.n; i++)
		for (int j = 0; j < re.m; j++)
			re.a[i][j] = 0;
	
	for (int k = 0; k < x.m; k++)
		for (int i = 0; i < re.n; i++)
			for (int j = 0; j < re.m; j++)
				re.a[i][j] = (re.a[i][j] + (x.a[i][k] * y.a[k][j]) % m) % m;
	
	return re;
}

void jzksm(int now) {
	b = a;
	now--;
	while (now) {
		if (now & 1) b = b * a;
		a = a * a;
		now /= 2;
	}
} 

int main() {
	scanf("%d %d", &n, &m);
	while (n || m) {
		a.n = 16;
		a.m = 16;
		memset(a.a, 0, sizeof(a.a));
		a.a[0][0] = 1 % m;a.a[3][0] = 1 % m;a.a[9][0] = 1 % m;a.a[12][0] = 1 % m;a.a[15][0] = 1 % m;
		a.a[2][1] = 1 % m;a.a[8][1] = 1 % m;a.a[14][1] = 1 % m;
		a.a[1][2] = 1 % m;a.a[13][2] = 1 % m;
		a.a[0][3] = 1 % m;a.a[12][3] = 1 % m;
		a.a[8][4] = 1 % m;a.a[11][4] = 1 % m;
		a.a[10][5] = 1 % m;
		a.a[9][6] = 1 % m;
		a.a[8][7] = 1 % m;
		a.a[1][8] = 1 % m;a.a[4][8] = 1 % m;a.a[7][8] = 1 % m;
		a.a[0][9] = 1 % m;a.a[6][9] = 1 % m;
		a.a[5][10] = 1 % m;
		a.a[4][11] = 1 % m;
		a.a[0][12] = 1 % m;a.a[3][12] = 1 % m;
		a.a[2][13] = 1 % m;
		a.a[1][14] = 1 % m;
		a.a[0][15] = 1 % m;
		
		jzksm(n);
		printf("%lld\n", b.a[0][0]);
		
		scanf("%d %d", &n, &m);
	}
	
	return 0;
} 
           

dfs求矩陣法

dfs 來求是打完表才想到的一個做法。

我們枚舉列，然後維護現在是從多少号轉移到多少号

就是要麼橫着放，要麼豎着放。

豎着放就是至少要有兩列，然後之前也要橫着放。

如果豎着放，那要麼就是凸出來，要麼就沒有凸出來。

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

struct matrix {
	int n, m;
	ll a[21][21];
}a, b, re;
int n, m;
matrix operator *(matrix x, matrix y) {
	re.n = x.n;
	re.m = y.m;
	for (int i = 0; i < re.n; i++)
		for (int j = 0; j < re.m; j++)
			re.a[i][j] = 0;
	
	for (int k = 0; k < x.m; k++)
		for (int i = 0; i < re.n; i++)
			for (int j = 0; j < re.m; j++)
				re.a[i][j] = (re.a[i][j] + (x.a[i][k] * y.a[k][j]) % m) % m;
	
	return re;
}

void jzksm(int now) {
	b = a;
	now--;
	while (now) {
		if (now & 1) b = b * a;
		a = a * a;
		now /= 2;
	}
} 

void dfs(int now, int pre, int nxt) {
	if (now == 4) {
		a.a[pre][nxt] = (a.a[pre][nxt] + 1) % m;
		return ;
	}
	
	dfs(now + 1, (pre << 1), (nxt << 1) + 1);//這個位置放一個橫的
	dfs(now + 1, (pre << 1) + 1, (nxt << 1));//之前的位置已經放了橫的
	if (now <= 2) dfs(now + 2, pre << 2, nxt << 2);//放一個縱的
}

int main() {
	scanf("%d %d", &n, &m);
	while (n || m) {
		a.n = 16;
		a.m = 16;
		memset(a.a, 0, sizeof(a.a));
		dfs(0, 0, 0);
		
		jzksm(n);
		printf("%lld\n", b.a[0][0]);
		
		scanf("%d %d", &n, &m);
	}
	
	return 0;
}