poj3519 Lucky Coins Sequence矩陣快速冪

Lucky Coins Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 608 Accepted Submission(s): 319

Problem Description
As we all know,every coin has two sides,with one side facing up and another side facing down.Now,We consider two coins's state is same if they both facing up or down.If we have N coins and put them in a line,all of us know that it will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins's state are same.How many different Lucky Coins Sequences exist?

Input
There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9.

Output
You should output the ways of lucky coins sequences exist with n coins ,but the answer will be very large,so you just output the answer module 10007.

Sample Input
3
4

Sample Output
2
6

Source
2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU
分析題意，我們可以發現就是dp,怎麼求遞推公式呢？dp[i][j]表示，有i位長，j最後幾位是相連的！
dp[i][3]=dp[i-1][2];

dp[i][2]=dp[i-1][1];

dp[i][1]=dp[i-1][1]+dp[i-1][2];

dp[1][1]=2;dp[1][2]=0;dp[1][3]=0;

這樣，我們就可以轉化為矩陣求和了！

include <iostream>  
#include <stdio.h>  
#include <string.h>  
using namespace std;  
#define mod 10007  
  
struct node {  
   int  m[4][4];  
    node operator *(node b) const//重載乘法  
    {  
        int i,j,k;  
        node c;  
        for(i=0;i<4;i++)  
            for(j=0;j<4;j++)  
            {  
                c.m[i][j]=0;  
                for(k=0;k<4;k++)  
                {  
                    c.m[i][j]+=m[i][k]*b.m[k][j];  
                    c.m[i][j]%=mod;//都要取模  
                }  
            }  
        return c;  
    }  
};  
node original,result;  
void quickm(int n)  
{  
    node a,b;  
    b=original;a=result;  
    while(n)  
    {  
        if(n&1)  
        {  
          b=b*a;  
        }  
        n=n>>1;  
        a=a*a;  
    }  
    printf("%d\n",2*b.m[0][3]%mod);  
}  
int main ()  
{  
  
    int i,j,n;  
    for(i=0;i<4;i++)  
        for(j=0;j<4;j++)  
        {  
            original.m[i][j]=(i==j)?1:0;//初始化為單位矩陣  
        }  
    memset(result.m,0,sizeof(result.m));  
    result.m[0][0]=result.m[0][1]=result.m[1][0]=result.m[1][2]=result.m[2][3]=1;  
    result.m[3][3]=2;  
    while(scanf("%d",&n)!=EOF)  
    {  
  
        quickm(n);  
    }  
    return 0;  
}