Lucky Coins Sequence

/*题意：定义一个硬币序列，如果超过三个相邻的硬币的正反相同，那么这个序列就是Lucky序列，给出序列    长度n，问有几种Lucky序列初步思路：这种题型一般都是递推过来的，不管了先打表试一下    打表结果：（从3开始的）        2        6        16        38        86        188        402        846        1760        3630        7438        15164        30794        62342        125904        253782        510758        1026684    每项和前项的二倍差的数刚好是一个变形的斐波那契数列。    得到递推公式：G(n)=2*(G(n-1)+F(n-2));#感悟：一边AC爽*/#include<bits/stdc++.h>#define mod 10007using namespace std;/********************************矩阵模板**********************************/class Matrix {    public:        int a[3][3];         void init(int x) {            memset(a,0,sizeof(a));            if(x==1){                a[0][0]=2;                a[0][1]=1;                a[0][2]=1;            }else{                a[0][0]=2;                a[1][0]=2;                a[1][1]=1;                a[1][2]=1;                a[2][1]=1;            }        }        Matrix operator +(Matrix b) {            Matrix c;            for (int i = 0; i < 3; i++)                for (int j = 0; j < 3; j++)                    c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;            return c;        }        Matrix operator +(int x) {            Matrix c = *this;            for (int i = 0; i < 3; i++)                c.a[i][i] += x;            return c;        }        Matrix operator *(Matrix b)        {            Matrix p;            memset(p.a,0,sizeof p.a);            for (int i = 0; i < 3; i++)                for (int j = 0; j < 3; j++)                for (int k = 0; k < 3; k++)                    p.a[i][j] = (p.a[i][j] + (a[i][k]*b.a[k][j])%mod) % mod;            return p;        }        Matrix power_1(int t) {            Matrix ans,p = *this;            memset(ans.a,0,sizeof ans.a);            for(int i=0;i<3;i++) ans.a[i][i]=1;            while (t) {                if (t & 1)                    ans=ans*p;                p = p*p;                t >>= 1;            }            return ans;        }                Matrix power_2(Matrix a,Matrix b,int x){            while(x){                if(x&1){                    b=a*b;                }                a=a*a;                x>>=1;            }            return b;        }}unit,init;/********************************矩阵模板**********************************/int n;int main(){    // freopen("in.txt","r",stdin);    while(scanf("%d",&n)!=EOF){        if(n<3){            printf("0\n");            continue;        }        if(n==3){            printf("2\n");            continue;        }        unit.init(1);        init.init(0);        // for(int i=0;i<3;i++){            // for(int j=0;j<3;j++){                // cout<<unit.a[i][j]<<" ";            // }            // cout<<endl;        // }        init=init.power_1(n-3);        printf("%d\n",(unit*init).a[0][0]);    }    return 0;}