hdu4990 转移矩阵

找了半天错发现m有可能是1.。

/*
如果n是奇数，就进行(n/2)次转移，然后取F[2]，反之取F[1] 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m,F[10];
struct Mat{
    ll m[10][10];
    Mat(){memset(m,0,sizeof m);}
};
void mul1(ll F[],Mat A){
    ll C[10]={};
    for(int j=0;j<3;j++)
        for(int i=0;i<3;i++)
            C[j]=(C[j]+F[i]*A.m[i][j]%m)%m;
    memcpy(F,C,sizeof C);
}
void mul2(Mat & A,Mat B){
    Mat C;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j]%m)%m;
    memcpy(A.m,C.m,sizeof C.m);
}
int main(){
    while(cin>>n>>m){
        memset(F,0,sizeof F);
        F[0]=1,F[1]=0,F[2]=1;
        Mat A;
        A.m[0][0]=A.m[0][2]=1;
        A.m[2][1]=2,A.m[2][2]=4;
        
        if(n==1){
            cout<<1%m<<endl;
            continue;
        }
        
        int flag=n%2;
        n/=2;
        while(n){
            if(n%2)
                mul1(F,A);
            mul2(A,A);
            n>>=1;
        }
        cout<<F[1+flag]%m<<endl;
    }
}