POJ 3420 Quad Tiling

标签：const int rep 3420 POJ ans Quad include mod

Description

Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:

In how many ways can you tile a 4 × N (1 ≤ N ≤ 10⁹) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 10⁵).

Input

Input consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.

Output

For each test case, output the answer modules M.

Sample Input

1 10000 3 10000 5 10000 0 0

Sample Output

1 11

95

由于宽度只有4，所以我们可以用[0,15]这16个数字的二进制形式来表示每一行的状态，

然后考虑状态的转移情况，这一行的状态从前一行的那些状态转移而来。

这样我们可以得到一个16*16的矩阵，然后给出初始的1*16的矩阵。

接下来就是矩阵快速幂了。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
//const int mod = 1e9 + 7;
const int N = 15;
int T, n, mod;
int a[N + 1][N + 1], b[N + 1][N + 1], c[N + 1][N + 1], ans[N + 1];

int main()
{
	rep(i, 0, N) a[i][i ^ N] = 1;
	rep(i, 0, N)
	{
		if ((i & 3) == 3) a[N ^ i ^ 3][i] = 1;
		if ((i & 6) == 6) a[N ^ i ^ 6][i] = 1;
		if ((i & 12) == 12) a[N ^ i ^ 12][i] = 1;
		if (i == N) a[i][i] = 1;
	}
	while (scanf("%d%d", &n, &mod) != EOF, n&&mod)
	{
		rep(i, 0, N) rep(j, 0, N) b[i][j] = a[i][j];
		memset(ans, 0, sizeof(ans));
		ans[N] = 1;
		for (; n; n >>= 1)
		{
			if (n & 1)
			{
				rep(i, 0, N)
				{
					c[0][i] = 0;
					rep(j, 0, N)
					{
						c[0][i] = (c[0][i] + 1LL * ans[j] * b[j][i]) % mod;
					}
				}
				rep(i, 0, N) ans[i] = c[0][i];
			}
			rep(i, 0, N) rep(j, 0, N)
			{
				c[i][j] = 0;
				rep(k, 0, N)
				{
					c[i][j] = (c[i][j] + 1LL * b[i][k] * b[k][j]) % mod;
				}
			}
			rep(i, 0, N) rep(j, 0, N) b[i][j] = c[i][j];
 		}
		printf("%d\n", ans[N]);
	}
	return 0;
}

标签：const,int,rep,3420,POJ,ans,Quad,include,mod
From： https://blog.51cto.com/u_15870896/5838892