題目描述：用1*2 的矩形通過組合拼成大矩形，求拼成指定的大矩形有幾種拼法。
首先 我們先求用1*2 的矩形拼成 n*m的矩形有多少種拼法
當n*m為奇數時，一定是不會拼出來的，因為想要拼出來就需要整數倍的小矩形數目。
為了加速算法，要把m，n中小的那個當做列
分兩個步驟：1） 先求出相鄰兩行的轉化關系
2） 通過相鄰兩行的轉化關系算出經過n次轉化有幾種方法能拼成n*m的矩陣
1） 狀態標記 橫放和豎放的下一個均為1，豎放的上一個和不放置為0 ，每行可以轉化為1個2進制數。當這一行訪問結束時，就會得到上一行狀態，和該行狀態，因為所有情況都是我們設置的，所以pre狀態一定會轉化為now狀態
對於每一個位置，我們有三種放置方法：1. 豎直放置2. 水平放置3. 不放置
d為當前列號 ，初始化d, now, pre都為0。now為當前行，pre為當前行的上一行
1. d = d + 1, now << 1 | 1, pre << 1; // 豎直放置，當前行該列為1，上一行該列置為為0
2. d = d + 2, now << 2 | 3, pre<< 2 | 3; // 橫放 都為11
3. d = d + 1, now << 1, pre<< 1 | 1; // 上一行該列置為1，不能豎放，不放置的狀態
因為轉移狀態有很多種，所以用dfs去枚舉各種可行的狀態。
下面是dfs實現：
2） 求出來相鄰兩行之間的狀態轉化，下面就要求經過n次轉化後最後狀態為(1<<m - 1) 的總數，對於n比較小（可用矩陣存儲） 的時候可用
當n很大的時候，就不能用上述的方法算了，這個時候矩陣的優勢就體現出來了
同樣是求經過n次轉化，從初始態到終態有幾種轉化法
建立矩陣的方法很簡單，矩陣的大小為（1<<m-1） 如過pre狀態能到達狀態now，那麼++matrix[pre][now]; 然後求此矩陣的n次冪即可
1、poj2411 題意：給定一個長寬小於等於11的矩形，問用1×2的小矩形填滿，有多少種方法。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=13;
int w,h,tan;
LL dp[13][2100];//1<<11
int path[14000][2];//11*(1<<11)
void dfs(int l,int now,int pre)
{
if(l>w)return;
if(l==w)
{
path[tan][0]=pre;
path[tan++][1]=now;
return ;
}
dfs(l+2,(now<<2)|3,(pre<<2)|3);
dfs(l+1,(now<<1)|1,pre<<1);
dfs(l+1,now<<1,(pre<<1)|1);
}
int main()
{
while(~scanf("%d%d",&h,&w))
{
if(!h&&!w)break;
if(h<w){int t=h;h=w;w=t;}
tan=0;
dfs(0,0,0);
memset(dp,0,sizeof(dp));
dp[0][(1<<w)-1]=1;
for(int i=0;i<h;++i)
{
for(int j=0;j<tan;++j)
{
dp[i+1][path[j][1]]+=dp[i][path[j][0]];
}
}
printf("%lld\n",dp[h][(1<<w)-1]);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=13;
int w,h,tan;
LL dp[13][2100];//1<<11
int path[14000][2];//11*(1<<11)
void dfs(int l,int now,int pre)
{
if(l>w)return;
if(l==w)
{
path[tan][0]=pre;
path[tan++][1]=now;
return ;
}
dfs(l+2,(now<<2)|3,(pre<<2)|3);
dfs(l+1,(now<<1)|1,pre<<1);
dfs(l+1,now<<1,(pre<<1)|1);
}
int main()
{
while(~scanf("%d%d",&h,&w))
{
if(!h&&!w)break;
if(h<w){int t=h;h=w;w=t;}
tan=0;
dfs(0,0,0);
memset(dp,0,sizeof(dp));
dp[0][(1<<w)-1]=1;
for(int i=0;i<h;++i)
{
for(int j=0;j<tan;++j)
{
dp[i+1][path[j][1]]+=dp[i][path[j][0]];
}
}
printf("%lld\n",dp[h][(1<<w)-1]);
}
return 0;
}
2、poj2663 題意：給定1*2的小矩形，去拼接一個3*n（n<30）的矩形，問有多少種方案。
3、poj3420 題意：給定1*2的小矩形，去拼接一個4*n（n<10^9）的矩形，問有多少種方案。N這麼大遞推肯定是不行了，所以我們要用矩陣快速冪進行加速，這個轉移矩陣如何構造呢，我們可以直接用pre狀態轉移到now狀態采用鄰接矩陣的方式表述就好了。這個矩陣的大小為at[16][16]，at[15][15]就是最後要求的狀態
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
struct mat{
LL at[16][16];
};
mat dat;
int n,mod;
void dfs(int l,int now,int pre)
{
if(l>4)return;
if(l==4)
{
++dat.at[pre][now];
return;
}
dfs(l+1,(now<<1)|1,(pre<<1));
dfs(l+1,(now<<1),(pre<<1)|1);
dfs(l+2,(now<<2)|3,(pre<<2)|3);
}
mat mul(mat a,mat b)
{
mat c;
memset(c.at,0,sizeof(c.at));
for(int i=0;i<16;++i)
{
for(int k=0;k<16;++k)
{
if(a.at[i][k])
{
for(int j=0;j<16;++j)
{
c.at[i][j]+=a.at[i][k]*b.at[k][j];
if(c.at[i][j]>=mod){c.at[i][j]%=mod;}
}
}
}
}
return c;
}
mat expo(mat a,int k)
{
if(k==1)return a;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i<16;++i){e.at[i][i]=1;}
if(k==0)return e;
while(k)
{
if(k&1)e=mul(a,e);
a=mul(a,a);
k>>=1;
}
return e;
}
int main()
{
memset(dat.at,0,sizeof(dat.at));
dfs(0,0,0);
while(~scanf("%d%d",&n,&mod))
{
if(!n&&!mod)break;
if(mod==1){printf("0\n");continue;}
mat ans=expo(dat,n);
printf("%lld\n",ans.at[15][15]);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
struct mat{
LL at[16][16];
};
mat dat;
int n,mod;
void dfs(int l,int now,int pre)
{
if(l>4)return;
if(l==4)
{
++dat.at[pre][now];
return;
}
dfs(l+1,(now<<1)|1,(pre<<1));
dfs(l+1,(now<<1),(pre<<1)|1);
dfs(l+2,(now<<2)|3,(pre<<2)|3);
}
mat mul(mat a,mat b)
{
mat c;
memset(c.at,0,sizeof(c.at));
for(int i=0;i<16;++i)
{
for(int k=0;k<16;++k)
{
if(a.at[i][k])
{
for(int j=0;j<16;++j)
{
c.at[i][j]+=a.at[i][k]*b.at[k][j];
if(c.at[i][j]>=mod){c.at[i][j]%=mod;}
}
}
}
}
return c;
}
mat expo(mat a,int k)
{
if(k==1)return a;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i<16;++i){e.at[i][i]=1;}
if(k==0)return e;
while(k)
{
if(k&1)e=mul(a,e);
a=mul(a,a);
k>>=1;
}
return e;
}
int main()
{
memset(dat.at,0,sizeof(dat.at));
dfs(0,0,0);
while(~scanf("%d%d",&n,&mod))
{
if(!n&&!mod)break;
if(mod==1){printf("0\n");continue;}
mat ans=expo(dat,n);
printf("%lld\n",ans.at[15][15]);
}
return 0;
}
