哈哈，寫了好久的，總算對了。

接下來介紹兩種思路：

先介紹一種 ? 遞推+矩陣的快速冪的方法

? 一種DP的思想考慮4×n的最后一列 ?，可以放的方法一共有5種

? ?1.放4個 1×2 ?則 為dp[n-2]

? 2. ? 放2個 2x1 ?則為 dp[n-1]

? 3. ? 放 1x2 ? ?2x1 ?1x2 ?則為 ?dp[n-2]+dp[n-4]+.....+dp[0]

?4. ?放 1x2 ?1x2 ?2x1 為 dp[n-2]+dp[n-3]+dp[n-4]+....+dp[0]

5.和 4 一樣 的另外一種情況 所以也是 dp[n-2]+dp[n-3]+....dp[0];

所以最后結果是 dp[n]=dp[n-1]+dp[n-2]+2*(dp[n-2]+dp[n-3]+..dp[0])+dp[n-2]+dp[n-4]+...dp[0];

然后寫一個dp[n-2]=..... ?

減一下，化簡 之后的結果是dp[n]=dp[n-1]+5*dp[n-2]+dp[n-3]-dp[n-4]; ?這就是遞推公式了

之后建立一個矩陣

（ 1 5 1 -1

? ? 1 0 0 0

? ? 0 1 0 0

? ? 0 0 1 0 ? ? ? ?）

dp[0]=1,dp[1]=1,dp[2]=5,dp[3]=11 ?不斷左乘那個矩陣 就可以轉化為 那個矩陣的 冪，之后快速冪搞定！！

最后答案注意點，可能為負，那只要 ?(ans+m)%m ?就是正確答案了！。

#include<cstdio> #include<cstring> #include<iostream> using namespace std; struct matri {long long f[4][4]; }; long long n,m; long long dp[5]; matri mul(matri a,matri b) {int i,j,k;matri c;memset(c.f,0,sizeof(c.f));for(i=0;i<4;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j])%m;return c; } void eps_mul(matri a,int t) {matri s;memset(s.f,0,sizeof(s.f));s.f[0][0]=s.f[1][1]=s.f[2][2]=s.f[3][3]=1;while(t){if(t&1)s=mul(s,a);a=mul(a,a);t=t>>1;}long long ans=0;for(int i=0;i<4;i++)ans=(ans+dp[i]*s.f[0][3-i]);if((ans%=m)<0) ans=(ans+m)%m;printf("%lld\n",ans); } int main() {dp[0]=1;dp[1]=1;dp[2]=5;dp[3]=11;while(scanf("%lld%lld",&n,&m),n||m){if(n<4) {printf("%lld\n",dp[n]%m);continue;}matri ss;ss.f[0][0]=1;ss.f[0][1]=5;ss.f[0][2]=1;ss.f[0][3]=-1;ss.f[1][0]=1;ss.f[1][1]=0;ss.f[1][2]=0;ss.f[1][3]=0;ss.f[2][0]=0;ss.f[2][1]=1;ss.f[2][2]=0;ss.f[2][3]=0;ss.f[3][0]=0;ss.f[3][1]=0;ss.f[3][2]=1;ss.f[3][3]=0;eps_mul(ss,n-3);} }

接下來講第二種狀態(tài)壓縮的方法

很顯然會有1<<4中狀態(tài)

各個狀態(tài)的匹配就達到了16*16 的矩陣。

矩陣的轉移快速冪的意思就是1,2 ? 3,4是同樣的。``同理。

狀態(tài)的轉移 很巧妙的就是矩陣的相乘，

#include<cstdio> #include<cstring> #include<iostream> using namespace std; struct matrix {int f[16][16]; }; int n,m; int pre[16*16],now[16*16]; int top; void dfs(int num,int p,int q) {if(num>4)return;if(num==4){pre[top]=q;now[top++]=p;return;}dfs(num+2,(p<<2)|3,(q<<2)|3);dfs(num+1,(p<<1)|1,q<<1);dfs(num+1,p<<1,(q<<1)|1); } matrix mul(matrix a,matrix b) {matrix s;memset(s.f,0,sizeof(s.f));int i,j,k;for(i=0;i<16;i++)for(j=0;j<16;j++)for(k=0;k<16;k++)s.f[i][j]=(s.f[i][j]+a.f[i][k]*b.f[k][j])%m;return s; } void quick_pow(matrix A,int k) {int i;matrix s;memset(s.f,0,sizeof(s.f));for(i=0;i<16;i++)s.f[i][i]=1;while(k){if(k&1)s=mul(s,A);A=mul(A,A);k=k>>1;}printf("%d\n",s.f[15][15]); } int main() {while(scanf("%d%d",&n,&m),n||m){int i;matrix s;memset(s.f,0,sizeof(s.f));top=0;dfs(0,0,0);for(i=0;i<top;i++)s.f[pre[i]][now[i]]=1;quick_pow(s,n);} }

所以可以寫出代碼

總結

以上是生活随笔為你收集整理的POj 3420 Quad Tiling 状态压缩DP+递推+矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。