POJ-3420 : Quad Tiling

問題概要

4*N(N<10^9)のマスにドミノを敷き詰める方法が何通りあるか求める問題。

解法

S=4とする。3^S*S(全てのビットに対し、部分集合を選んで、その部分集合に含まれるビットは横向きになっていると思う)で遷移行列を計算して後は行列累乗で加速する。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

typedef long long int64;
typedef int64 mat_t;

int64 MOD;

const int S = 4;
int N;

bool init() {
	scanf("%d%lld", &N, &MOD);
	return N > 0;
}

int solve() {
	
	Matrix mat(1<<S, 1<<S);
	for (int bit = 0; bit < 1<<S; ++bit) {
		for (int sub = bit; ; sub = bit & (sub - 1) ) {
			const int prevMask = ((1<<S) - 1) ^ sub;
			const int cur = bit ^ sub;
			bool ok = true;
			int cont = 0;
			for (int i = 0; i < S; ++i) {
				if ((cur>>i)&1) {
					++cont;
				}
				else {
					ok &= cont % 2 == 0;
					cont = 0;
				}
			}
			ok &= cont % 2 == 0;
			if (ok) {
				++mat[bit][prevMask];
			}
			if (sub == 0) {
				break;
			}
		}
	}

	for (int i = 0; i < 1<<S; ++i) {
		for (int j = 0; j < 1<<S; ++j) {
			if (mat[i][j]) {
			}
		}
	}

	vector<int64> ini(1<<S, 0);
	ini[(1<<S)-1] = 1;
	vector<int64> ans = pow(mat, N) * ini;
	return int(ans[(1<<S)-1] % MOD);
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}

	return 0;
}