HDU3893之矩陣快速冪

Drawing Pictures
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 467    Accepted Submission(s): 207

Problem Description
Dr. Skywind is drawing a picture, using his favorite six colors, namely red, orange, yellow, green, blue, and violet.
The paper has N grids in a line. Each time he will fill a grid with one of the six colors. All grids needs to be filled. To make his drawing more beautiful, Skywind decided to draw symmetrically. Moreover, as he hates sorting, Skywind will never come up with the situation where all colors are in their original order. So he won't draw red-orange-yellow-green-blue-violet in a continuous way. And to make his drawing clearer, he won't paint the same color in adjacent grids.
Given N, you are asked to calculate the number of ways that Skywind can complete his drawing. As the answer might be very large, just output the number MOD 112233.

Input
There are multiple test cases ended with an EOF. Each test case will be a line containing one positive integer N. (N <= 10^9)

Output
For each test case, output the answer MOD 112233 in a single line.

Sample Input
2
5

Sample Output
0
150

題意：給n個格子用6種顏色去填,相鄰顏色不能相同,不能1，2，3，4，5，6六種顏色連續在一起,前後要對稱,求有多少種可能

/*分析:假設 
dp[i][0]表示長度為i的全部有效數 
dp[i][5]表示長度為i的以12345結尾的有效數(方便dp[i][0]減去654321xxx,123456xxx這種) 
dp[i][4]表示長度為i的以1234結尾的有效數(方便得到dp[i][5]) 
dp[i][3]表示長度為i的以123結尾的有效數(方便得到dp[i][4]) 
dp[i][2]表示長度為i的以12結尾的有效數(方便得到dp[i])[3] 
dp[i][1]表示長度為i的以1結尾的有效數(方便得到dp[i][2]) 
則: 
dp[i][0]=5*dp[i-1][0]-2*dp[i][5];//減去654321,123456這種 
dp[i][5]=dp[i-1][4]; 
dp[i][4]=dp[i-1][3]; 
dp[i][3]=dp[i-1][2] 
dp[i][2]=dp[i-1][1]; 
dp[i][1]=dp[i][0]-dp[i-1][1]-dp[i][5];//減去11xxx,123456xxx這種 
然後用矩陣快速冪求dp[n][0] 
*/  
#include<iostream>   
#include<cstdio>   
#include<cstdlib>   
#include<cstring>   
#include<string>   
#include<queue>   
#include<algorithm>   
#include<map>   
#include<iomanip>   
#define INF 99999999   
using namespace std;  
  
const int MAX=6;  
const int mod=112233;  
__int64 array[MAX][MAX],sum[MAX][MAX];  
  
void MatrixMult(__int64 a[MAX][MAX],__int64 b[MAX][MAX]){  
    __int64 c[MAX][MAX]={0};  
    for(int i=0;i<MAX;++i){  
        for(int j=0;j<MAX;++j){  
            for(int k=0;k<MAX;++k){  
                c[i][j]+=a[i][k]*b[k][j];  
            }  
        }  
    }  
    for(int i=0;i<MAX;++i){  
        for(int j=0;j<MAX;++j)a[i][j]=c[i][j]%mod;  
    }  
}  
  
__int64 Matrix(int k){  
    memset(array,0,sizeof array);  
    array[0][0]=5,array[0][1]=-2;  
    array[1][2]=array[2][3]=array[3][4]=array[4][5]=array[5][0]=1;  
    array[5][1]=array[5][5]=-1;  
    for(int i=0;i<MAX;++i){//初始化sum使sum*a=a    
        for(int j=0;j<MAX;++j)sum[i][j]=(i == j);  
    }  
    while(k){  
        if(k&1)MatrixMult(sum,array);  
        MatrixMult(array,array);  
        k>>=1;  
    }  
    return ((sum[0][0]*6+sum[0][5])%mod+mod)%mod;//dp[1][0]=6,dp[1][1]=1,dp[1][i]=0(i != 1 && i != 0)   
}  
  
int main(){  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        if(n%2 == 0)printf("0\n");//偶數由於對稱中間兩個一定相等所以沒有符合的    
        else{  
            n=n/2+1;  
            printf("%I64d\n",Matrix(n-1));//dp是從長度1開始,所以只需要矩陣相乘n-1次就是長度為n的結果    
        }  
    }  
    return 0;  
}