2020牛客寒假算法基础集训营1 u's的影响力

题意

　　设第 i 天的影响力为  ，那么  ，，对于  ， 。

　　她们想知道第  天影响力是多少？
　　由于这个数可能非常大，只需要输出其对  取模的值就可以了。

题解

　　费马小定理 + 矩阵快速幂。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
struct matrix
{
    long long M[3][3];
    matrix operator * (const matrix & other) const
    {
        matrix ans;
        fill(ans.M[0],ans.M[0]+9,0);
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)
                    ans.M[i][j]=(ans.M[i][j]+M[i][k]*other.M[k][j]%(mod-1))%(mod-1);
        return ans;
    }
};
matrix quick(matrix a,long long b);
long long quick(long long a,long long b);
long long n,x,y,a,b;
int main()
{
    long long ans,p,q;

    scanf("%lld%lld%lld%lld%lld",&n,&x,&y,&a,&b);
    a%=mod;x%=mod;y%=mod;b%=mod-1;

    matrix mat,pre={1,1,b,1,0,0,0,0,1};
    
    if(n==1) printf("%lld",x);
    else if(n==2) printf("%lld",y);
    else
    {
        if(a==0||x==0||y==0) 
            printf("0
");
        else
        {
            mat=quick(pre,n-2);
            ans=((quick(x,mat.M[0][1])%mod*quick(y,mat.M[0][0])%mod)%mod*quick(a,mat.M[0][2])%mod)%mod;
            printf("%lld",ans);
        }
    }
    system("pause");
    return 0;
}
matrix quick(matrix a,long long b)
{
    matrix ans;
    fill(ans.M[0],ans.M[0]+9,0);
    ans.M[0][0]=ans.M[1][1]=ans.M[2][2]=1;
    while(b)
    {
        if(b&1)
            ans=ans*a;
        b/=2;
        a=a*a;
    }
    return ans;
}
long long quick(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return ans;
}