矩阵求fibonacci——hdu2855

http://acm.hdu.edu.cn/showproblem.php?pid=2855

实际就是求fibonacci的2*n个

用二分矩阵算

#include<stdio.h>
#include<string.h>

int mod;

struct data
{
    int map[2][2];
};

data matrix(data a,data b)//矩阵乘法
{
    int n=2;
    int i,j,k;
    data re;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            int all=0;
            for(k=0;k<n;k++)
            {
                all+=(a.map[i][k]*b.map[k][j])%mod;
                all%=mod;
            }
            re.map[i][j]=all%mod;
        }
    }
    return re;
}

data matrixT(int p)//二分求矩阵
{
    data f;
    
    int i,j;
    data all;
    all.map[0][0]=0;//单位矩阵
    all.map[1][0]=1;
    all.map[0][1]=1;
    all.map[1][1]=0;
    int n=2;
    
    f.map[0][0]=0;
       f.map[0][1]=1;
       f.map[1][0]=1;
       f.map[1][1]=1;
       
       while(p>0)//二分求矩阵
       {
           if(p&1==1)
           {all=matrix(all,f);}
           
           f=matrix(f,f);
           p>>=1;
       }
       
       return all;
}

int main()
{
    int p;
    int t;
    scanf("%d",&t);
    
    int n;
    while(t--)
    {
        scanf("%d%d",&n,&mod);

        data ret=matrixT(n*2);
        
        printf("%d\n",(ret.map[1][1])%mod);
    }
    
    return 0;
}