题意：

4*N的矩形中放入1*2的小矩形有多少种放法

分析：

表示公式不会推导。。没找着有人推公式的证明了。。。

求证明、、、

手动算出来前4项，然后处理线性递推式就好了~

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 struct MT 9 {10     int x,y;11     int mt[7][7];12 }ans,def;13 14 int n,m;15 16 inline MT operator *(MT a,MT b)17 {18     MT c;19     memset(c.mt,0,sizeof c.mt);20     c.x=a.x; c.y=b.y;21     for(int i=1;i<=a.x;i++)22         for(int j=1;j<=b.y;j++)23             for(int k=1;k<=a.y;k++)24                 c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k]%m)*(b.mt[k][j]%m))%m;25     return c;26 }27 28 void go()29 {30     while(n)31     {32         if(n&1) ans=def*ans;33         def=def*def;34         n>>=1;35     }36     printf("%d\n",ans.mt[4][1]);37 }38 39 bool prev()40 {41     if(n==1) {printf("%d\n",1%m);return false;}42     else if(n==2) {printf("%d\n",5%m);return false;}43     else if(n==3) {printf("%d\n",11%m);return false;}44     n-=4;45     46     memset(def.mt,0,sizeof def.mt);47     def.mt[1][2]=def.mt[2][3]=def.mt[3][4]=1;48     def.mt[4][1]=-1; def.mt[4][2]=1; def.mt[4][3]=5; def.mt[4][4]=1;49     def.x=def.y=4;50     51     ans.x=4; ans.y=1;52     ans.mt[1][1]=1; ans.mt[2][1]=5; ans.mt[3][1]=11; ans.mt[4][1]=36;53     return true;54 }55 56 int main()57 {58     while(scanf("%d%d",&n,&m),n)59     {60         if(!prev()) continue;61         else go();62     }63     return 0;64 }