poj 3420 Quad Tiling （状压dp+多米诺骨牌问题+矩阵快速幂）

还有这种操作？？？？？？

直接用pre到now转移的方式构造一个矩阵就好了。

二进制长度为m，就构造一个长度为1 << m的矩阵

最后输出ans[(1 << m) - 1][(1 << m) - 1]就好了

牛逼！

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 16;

struct mat

{

   ll m[MAXN][MAXN];

   mat() { memset(m, 0, sizeof(m)); }

}A;

int n, MOD;

mat operator *(const mat& a, const mat& b)

{

	mat res;

	REP(i, 0, MAXN)

		REP(j, 0, MAXN)

			REP(k, 0, MAXN)

				res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;

	return res;

}

void dfs(int l, int now, int pre)

{

	if(l > 4) return;

	if(l == 4)

	{

		A.m[pre][now]++;

		return;

	}

	dfs(l + 1, (now << 1) | 1, pre << 1);

	dfs(l + 1, now << 1, (pre << 1) | 1);

	dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);

}

mat pow(mat a, int b)

{

	mat res;

	REP(i, 0, MAXN) res.m[i][i] = 1;

	for(; b; b >>= 1)

	{

		if(b & 1) res = res * a;

		a = a * a;

	}

	return res;

}

int main()

{

	dfs(0, 0, 0);

	while(~scanf("%d%d", &n, &MOD) && n)

	{

		mat ans = pow(A, n);

		printf("%lld\n", ans.m[15][15]);

	}

	return 0;

}

巴特西

poj 3420 Quad Tiling （状压dp+多米诺骨牌问题+矩阵快速幂）

最新文章

热门文章