HDU 2604

快速冪取模，快速矩陣冪取模

先利用DFA構造轉移矩陣

 [cpp]
#include<cstdio> 
#include<cstring> 
using namespace std; 
typedef long long ll; 
int len,mod; 
ll tem[6][6]; 
int main(){ 
    int i,j,k; 
    while(scanf("%d %d",&len,&mod)==2){ 
        ll a[6][6]={{0,0,1,0,0,1},{0,0,0,0,0,1},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,2,0,1,0,0},{2,0,1,0,0,0}}; 
        ll t[6][6]={{1,0,0,0,0,0},{0,1,0,0,0,0},{0,0,1,0,0,0},{0,0,0,1,0,0},{0,0,0,0,1,0},{0,0,0,0,0,1}}; 
 
        int l=len; 
        while(l){ 
            if(l%2){ 
                for(i=0;i<=5;i++) 
                    for(j=0;j<=5;j++) 
                        for(k=0;k<=5;k++) 
                            tem[i][j]+=(t[i][k]*a[k][j])%mod; 
                for(i=0;i<=5;i++) 
                    for(j=0;j<=5;j++){ 
                        t[i][j]=tem[i][j]%mod; 
                        tem[i][j]=0; 
                    } 
            } 
            for(i=0;i<=5;i++) 
                for(j=0;j<=5;j++) 
                    for(k=0;k<=5;k++) 
                        tem[i][j]+=(a[i][k]*a[k][j])%mod; 
            for(i=0;i<=5;i++) 
                for(j=0;j<=5;j++){ 
                    a[i][j]=tem[i][j]%mod; 
                    tem[i][j]=0; 
                } 
            l/=2; 
        } 
 
        ll ans=1; 
        ll m=2; 
        while(len){ 
            if(len%2) 
                ans=(ans*m)%mod; 
            m=(m*m)%mod; 
            len/=2; 
        } 
        ans%=mod; 
        printf("%I64d\n",(ans+mod*2-t[5][5]-t[4][5])%mod); 
    } 
    return 0; 
}