【题解】sdoj3739 K-斐波那契（2018-08-08集训T2）矩阵快速幂+扩展欧几里得

题目链接

【样例输入 】
5 5
【样例输出】
2
【样例解释】
f[0] = 2
f[1] = 2
f[2] = 4
f[3] = 6 mod 5 = 1
f[4] = 5 mod 5 = 0
f[5] = 1
30%的数据保证 n, P ≤ 1000
100%的数据保证 n, P ≤ 10^9

---

比赛时不知道怎么做，枚举了30分。后来才知道用矩阵快速幂和扩展欧几里得（本蒟蒻啥也不会，赶紧去学了一发）

#include<cstdio>
#include<cstring>
typedef long long ll;
int n,p;
struct Matrix{
    ll mx[2][2];
    friend Matrix operator *(Matrix a,Matrix b)
    {
        Matrix c;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
            {
                c.mx[i][j]=0;
                for(int k=0;k<2;k++)
                    c.mx[i][j]=(c.mx[i][j]+a.mx[i][k]*b.mx[k][j])%p;
            }
        return c;
    }
    friend Matrix operator ^(Matrix a,int num)
    {
        Matrix c;
        memset(c.mx,0,sizeof(c.mx));
        for(int i=0;i<2;i++)
            c.mx[i][i]=1;
        while(num)
        {
            if(num&1)c=c*a;
            num>>=1;
            a=a*a;
        }
        return c;    
    }
};
bool exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;y=0;return a==1;
    }
    else if(!exgcd(b,a%b,y,x))return false;
    y-=a/b*x;return true;
}
int main()
{
    scanf("%d%d",&n,&p);
    Matrix base;
    base.mx[0][0]=1;
    base.mx[0][1]=1;
    base.mx[1][0]=1;
    base.mx[1][1]=0;    
    Matrix ans;
    ans=base^(n-1);//写成base^n,WA一万年 
    int a=(ans.mx[0][0]+ans.mx[1][0])%p,x,y;
    if(exgcd(a,p,x,y))
        printf("%d\n",(x+p)%p);
    else puts("None");
    return 0;
}