本文共 4475 字，大约阅读时间需要 14 分钟。
poj 2411
题意：让你用1*2的矩阵去填满n*m的方格，有多少种方法
题解：
#include #include #include #include using namespace std;typedef long long LL;#define M 1<<11+1LL dp[14][M];int st[M*11][2];int n,m,cnt;void dfs(int cur,int now,int pre){ if(cur > m) return ; if(cur == m){ st[cnt][0] = pre; st[cnt][1] = now; cnt ++; return ; } dfs(cur + 2,((now<<2)|3),((pre<<2)|3));//当前行横放为11，那么上一行填11 dfs(cur + 1,((now<<1)|1),(pre<<1));// 当前行竖放为1，那么上一行填0 dfs(cur + 1,(now<<1),((pre<<1)|1));// 如果上一行为1，那么当前行不放置为0}int main(){ while(scanf("%d%d",&n,&m) , n + m){ if(n < m) swap(n,m); cnt = 0; memset(st,0,sizeof(st)); dfs(0,0,0); memset(dp,0,sizeof(dp)); dp[0][(1< < n;i++) for(int j = 0;j < cnt;j++) dp[i+1][st[j][1]] += dp[i][st[j][0]]; cout << dp[n][(1< << endl; }}
解题方法与上题一样，题意 用1*2 的矩阵填充3*n的矩阵有多少种方法
#include #include #include #include using namespace std;typedef long long LL;#define M 100int dp[50][M];int st[M*11][2];int n,m,cnt;void dfs(int cur,int now,int pre){ if(cur > m) return ; if(cur == m){ st[cnt][0] = pre; st[cnt][1] = now; cnt ++; return ; } dfs(cur + 2,((now<<2)|3),((pre<<2)|3));//当前行横放为11，那么上一行填11 dfs(cur + 1,((now<<1)|1),(pre<<1));// 当前行竖放为1，那么上一行填0 dfs(cur + 1,(now<<1),((pre<<1)|1));// 如果上一行为1，那么当前行不放置为0}int main(){// freopen("1.txt","w",stdout); while(scanf("%d",&n)){ if(n < 0) break;// if(!n) {cout << 0 << endl;continue;} m = 3; if(n < m) swap(n,m); cnt = 0; memset(st,0,sizeof(st)); dfs(0,0,0); memset(dp,0,sizeof(dp)); dp[0][(1< < n;i++) for(int j = 0;j < cnt;j++) dp[i+1][st[j][1]] += dp[i][st[j][0]]; cout << dp[n][(1< << endl; }}
题意 用1*2 的矩阵填充4*n的矩阵有多少种方法（n比较大，用矩阵快速幂解决）
递推公式为 f（n） = f(n-1) + 5 * f(n-2) + f(n-3) - f(n-4)
构造矩阵
1 5 1 -1
1 0 0 0
0 1 0 0
0 0 1 0
此题还有一种方法：
#include #include #include #include using namespace std;typedef long long LL;LL mod;int n;struct Z{ LL m[4][4];};Z q = { 1,5,1,-1, 1,0,0,0, 0,1,0,0, 0,0,1,0};Z y = { 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1};Z operator * (Z a,Z b){ Z c; memset(c.m,0,sizeof(c.m)); for(int i = 0;i < 4;i++) for(int j = 0;j < 4;j++) for(int k = 0;k < 4;k++) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; return c;}Z Pow(int x){ Z ret,p; ret = y,p = q; while(x){ if(x&1) ret = p*ret ; p = p * p; x >>= 1; } return ret;}int main(){ int a[] = {1,1,5,11,36}; while(cin >> n >> mod,n+mod){ if(n < 5){cout << (a[n]%mod) << endl;continue;} Z r = Pow(n - 4); LL ans = (r.m[0][0]*36 + r.m[0][1] * 11 + r.m[0][2]*5 + r.m[0][3]) % mod; ans = (ans + mod) % mod; cout << ans << endl; }}
(状态压缩+矩阵乘法)
题意：同上 2<=n <= 10^9 && 2 <= m <= 5;
#include #include #include #include using namespace std;typedef long long LL;const LL mod = 1000000007;#define M 1<<5+1LL st[M][M];int n,m,cnt;struct Z{ LL m[32][32]; Z(){memset(m,0,sizeof(m));} void init(){ for(int i = 0;i < cnt;i++) m[i][i] = 1; }};void dfs(int cur,int now,int pre){ if(cur > m) return ; if(cur == m){ st[pre][now] = 1; return ; } dfs(cur + 2,((now<<2)|3),((pre<<2)|3));//当前行横放为11，那么上一行填11 dfs(cur + 1,((now<<1)|1),(pre<<1));// 当前行竖放为1，那么上一行填0 dfs(cur + 1,(now<<1),((pre<<1)|1));// 如果上一行为1，那么当前行不放置为0}Z operator * (Z a,Z b){ Z c; for(int i = 0;i < cnt ;i++) for(int k = 0;k < cnt ;k++) if(a.m[i][k]) for(int j = 0;j < cnt ;j++) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; return c;}Z pow(int n,Z a){ Z ret ;ret.init(); while(n){ if(n&1) ret = ret * a; a = a * a; n >>= 1; } return ret;}int main(){ while(~scanf("%d%d",&n,&m)){ if(n < m) swap(n,m); memset(st,0,sizeof(st)); dfs(0,0,0); cnt = 1 << m; Z s; for(int i = 0;i < cnt;i++) for(int j = 0;j < cnt;j++) s.m[i][j] = st[i][j]; s = pow(n,s); printf("%lld\n",s.m[cnt-1][cnt-1]); } return 0;}
转载地址：http://hdsgi.baihongyu.com/