牛客:μ's的影响力(矩阵快速幂)

原题链接:https://ac.nowcoder.com/acm/contest/3002/J

一篇讲矩阵快速幂的文章:https://blog.csdn.net/wust_zzwh/article/details/52058209 ,这篇文章只讲了点代码。刚接触矩阵快速幂是看了另一个人的文章,那个人把推理过程写出来了,看了推理过程就感觉对矩阵快速幂理解的差不多了(理解而非应用),奈何那篇文章没保存,找不到了。

这道题主要就是运用了矩阵快速幂和费马小定理

费马小定理:如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)

f(n)可以用x,y,a三个数相乘的形式表示出来

每一项a的幂次分别是 0、0、b、2b、4b、7b、12b……从第三项开始每一项为前两项之和加1。

而x和y的幂次构成斐波那契数列:x的幂次第一项是1,第二项是0;y的幂次第一项是0,第二项是1。之后每一项均为前两项之和。

用矩阵快速幂O(logn)求出斐波那契的第n项值

根据费马小定理,1e9+7是素数,a^(1e9+6) % 1e9+7 =1

所以可以对x、y、a的指数模1e9+6

最后用快速幂算出三个数再相乘就是最终结果

代码:

#include <bits/stdc++.h>
using namespace std;
long long m=1000000006,mod=1000000007;
long long n,x,y,a,b;
long long cx[3][3],cy[3][3],ca[3][3],tmp[3][3],opx[3][3],opy[3][3],opb[3][3];
void mutli(long long a[][3],long long b[][3],int N)
{
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {tmp[i][j]+=a[i][k]*b[k][j]%m;
            tmp[i][j]=tmp[i][j]%m;}
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {a[i][j]=tmp[i][j];}
    }
}
void pow(long long res[][3],long long a[][3])
{
    for(int i=0;i<2;i++)
    {res[i][i]=1;}
    long long N=n-2;
    while(N)
    {
        if(N&1)
        {mutli(res,a,2);}
        mutli(a,a,2);
        N>>=1;
    }
}
void powb(long long res[][3],long long a[][3])
{
    for(int i=0;i<3;i++)
    {res[i][i]=1;}
    long long N=n-5;
    while(N)
    {
        if(N&1)
        {mutli(res,a,3);}
        mutli(a,a,3);
        N>>=1;
    }
}
long long ksm(long long aa,long long bb)
{
    long long s=1;
    while(bb)
    {
        if(bb&1)
        {s=s*aa%mod;}
        aa=aa*aa%mod;
        bb>>=1;
    }
    return s;
}
int main()
{
    long long ans=0;
    cin>>n>>x>>y>>a>>b;
    if(n==1){cout<<x%mod<<endl;return 0;}
    if(n==2){cout<<y%mod<<endl;return 0;}
    if(x%mod==0||y%mod==0||a%mod==0)
    {cout<<"0"<<endl;
    return 0;}
    opx[0][0]=opx[0][1]=opx[1][0]=1;
    pow(cx,opx);
    opy[0][0]=opy[0][1]=opy[1][0]=1;
    pow(cy,opy);
    long long c=0;//c为a的指数的系数
    if(n<6)
    {
        if(n==5){c=4;}
        if(n==4){c=2;}
        if(n==1){c=1;}
    }
    else
    {   opb[0][0]=opb[0][1]=opb[0][2]=opb[1][0]=opb[2][2]=1;
        powb(ca,opb);
        c=(ca[0][0]*4+ca[0][1]*2+ca[0][2])%m;
    }
    long long cb=(c%m)*(b%m)%m;
    long long k1=(ksm(x%mod,cx[0][1])%mod);//下面几个式子要对x、y、a取模后再运算,当时没注意到在90%这卡了好久
    long long k2=(ksm(y%mod,cy[0][0])%mod);
    long long k3=(ksm(a%mod,cb)%mod);
    long long k4=k1*k2%mod;
    ans=k4*k3%mod;
    cout<<ans<<endl;
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注