hdu 3519繰返し+マトリクス高速べき乗

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=3519 題意:n個の硬貨が一列に並んでいて、正と逆があって、2個以上連続している同じ硬貨にいくつかの方案の分析があることを聞いています:典型的な推式は行列で急速にべき乗して解く題を使います.長さnの01列には2^nの異なる配列方法があり、f(n)を長さnとし、連続して3つ以上同じ1または0の01列を含まないとすると、f(1)=2,f(2)=4,f(3)=6,f(4)=10 n>4の場合、状況は1,00または11で終わると、それぞれf(n-2)がある/2の場合、加算するとf(n-2)種である.2、01または10で終わるとn番目のn文字とn-1番目の文字が異なる場合、それぞれf(n-1)/2種があり、加算するとf(n-1)であると統計するとf(n)=f(n-1)+f(n-2)であり、問題は同じ0または1列を3つ連続して含む列数を要求する.それはa[n]=(2^n-f(n))である%10007.しかし、これはまだ求めにくい.まず%10007を見ないで、繰返し式に変換するのはa[n]=a[n-1]+a[n-2]+2^(n-2)、行列に変換する:a[n]1 1 a[n-1]a[n-1]=1 0 0 0*a[n-2]2^(n-1)0 0 2^(n-2)
これによりマトリクスべき乗でa[n]を迅速に算出でき,複雑度はO(logn)である.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3;
const int mod=10007;
struct Mat{
    int mat[N][N];
};
Mat mul(Mat a,Mat b)
{
    Mat c;
    memset(c.mat,0,sizeof(c.mat));
    for(int k=0;k<N;k++)
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
    return c;
}
Mat qmod(Mat a,int k)
{
    Mat c;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        c.mat[i][j]=(i==j);
    for(;k;k>>=1){
        if(k&1)c=mul(c,a);
        a=mul(a,a);
    }
    return c;
}
int main()
{
    int n;
    int b[]={0,0,0,2,6};
    while(~scanf("%d",&n)){
        Mat a;
        a.mat[0][0]=a.mat[0][1]=a.mat[0][2]=1;
        a.mat[1][0]=1;a.mat[1][1]=a.mat[1][2]=0;
        a.mat[2][0]=a.mat[2][1]=0;a.mat[2][2]=2;
        if(n<=4){
            printf("%d
",b[n]);continue;
        }
        Mat c=qmod(a,n-4);
        int ans=c.mat[0][0]*6+c.mat[0][1]*2+c.mat[0][2]*8;
        printf("%d
",ans%mod);
    }
    return 0;
}