POJ 3734 Blocks

POJ 3734 Blocks

題目概述:腦書p.205

有n個格子，有紅、藍、綠、黃 四種顏色可以塗，每一個只能塗一種顏色。請問將紅色與綠色都塗在偶數個格子上的方法總數。

思路:

利用矩陣快速冪。

狀態為(紅和綠皆為偶數，紅和綠其一為奇數，紅和綠皆為奇數)。

轉移矩陣就看code吧~

AC code:

//By SCJ

#include<iostream>

#include<vector>

using namespace std;

#define endl '\n'

#define MOD 10007

typedef long long ll;

typedef vector<int> vec;

typedef vector<vec> mat;

mat mul(mat &A,mat &B)

{

   mat C(A.size(),vec(B[0].size()));

   for(int i=0;i<A.size();++i)

       for(int j=0;j<B[0].size();++j)

           for(int k=0;k<B.size();++k)

               C[i][j]=(C[i][j]+A[i][k]*B[k][j]%MOD)%MOD;

   return C;

}

mat POW(mat A,int n)

{

   mat res(A.size(),vec(A.size()));

   for(int i=0;i<A.size();++i) res[i][i]=1;

   mat base=A;

   while(n)

   {

       if(n&1) res=mul(base,res);

       base=mul(base,base);

       n>>=1;

   }

   return res;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   mat P(3,vec(3));

   P[0][0]=2;P[0][1]=1;P[0][2]=0;

   P[1][0]=2;P[1][1]=2;P[1][2]=2;

   P[2][0]=0;P[2][1]=1;P[2][2]=2;

   int T;cin>>T;

   while(T--)

   {

       int n;cin>>n;

       cout<<POW(P,n)[0][0]<<endl;

   }

}