POJ 3420 矩陣的冪

2019-11-10 20:53:21

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題目鏈接：

POJ-3420

題意：

用1×2的矩形填充4×n的的矩形，求方案數(shù)。

思路：

大家可以輕易地在網(wǎng)上找到狀態(tài)壓縮的解法，這里我給出一個遞推+矩陣的冪的方法。這里寫圖片描述

- a[n] = a[n-1]+b[n-1]+c[n-1]+dx[n-1]+dy[n-1] - b[n] = a[n-1] - c[n] = a[n-1]+e[n-1] - dx[n] = a[n-1]+dy[n-1] - dy[n] = a[n-1]+dx[n-1] - e[n] = c[n-1]

令d[n] = dx[n-1]+dy[n-1]可得—->

- a[n] = a[n-1]+b[n-1]+c[n-1]+d[n-1] - b[n] = a[n-1] - c[n] = a[n-1]+e[n-1] - d[n-1] = 2×a[n-1]+d[n-1] - e[n] = c[n-1]

所以就可以用矩陣來做了：A = |1 1 1 1 0| |1 0 0 0 0| |1 0 0 0 1| |2 0 0 1 0| |0 0 1 0 0| F[n] = F[n-1] × A

然后就可以輕松的使用矩陣快速冪了。下面附代碼：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define rep(i,x,y) for(int i = x;i < y;i++)#define fill(a,x) memset(a,x,sizeof(a))int n,mod;struct matrix{ int f[5][5];}a;void init(){ fill(a.f,0); a.f[0][1] = a.f[0][2] = a.f[0][3] = 1; a.f[0][0] = a.f[1][0] = a.f[2][0] = 1; a.f[2][4] = a.f[3][3] = a.f[4][2] = 1; a.f[3][0] = 2;}matrix mul(matrix a,matrix b){ matrix s; fill(s.f,0); rep(i,0,5) rep(j,0,5) rep(k,0,5) s.f[i][j] = (s.f[i][j] + a.f[i][k] * b.f[k][j]) % mod; return s;}matrix pows(matrix a,int b){ matrix s; rep(i,0,5) rep(j,0,5) if(i == j) s.f[i][j] = 1; else s.f[i][j] = 0; while(b) { if(b & 1) s = mul(s,a); a = mul(a,a); b = b >> 1; } return s;}int main(){ while(scanf("%d%d",&n,&mod) && n && mod) { init(); a = pows(a,n);