POJ 3420 矩阵的幂

2019-11-10 20:53:21

字体：大中小

来源：转载

供稿：网友

题目链接：

POJ-3420

题意：

用1×2的矩形填充4×n的的矩形，求方案数。

思路：

大家可以轻易地在网上找到状态压缩的解法，这里我给出一个递推+矩阵的幂的方法。这里写图片描述

- 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); PRintf("%d/n",a.f[0][0] % mod); } return 0;}

上一篇：bzoj1562 [NOI2009]变换序列

下一篇：【动态规划】最大子矩阵