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; }