首页 > 代码库 > BZOJ 3240 矩阵游戏

BZOJ 3240 矩阵游戏

矩阵不要乱用欧拉定理。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
#define maxn 1000050
using namespace std;
char n[maxn],m[maxn];
long long n1,n2,m1,m2,k,k1,k2,a,b,c,d,ans;
long long f_pow(long long a,long long b)
{
    long long base=a,ans=1;
    while (b)
    {
        if (b&1) ans=(ans*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return ans;
}
long long inv(long long a)
{
    return f_pow(a,mod-2);
}
long long ask(long long k1,long long k2)
{
    if (k1==1) return n1*k2%mod+1;
    return (f_pow(k1,n2)+(f_pow(k1,n2)-1+mod)%mod*inv(k1-1)%mod*k2%mod)%mod;
}
void work1()
{
    m1=(m1-1+mod)%mod;
    k1=c;k2=b*c%mod*m1%mod+d;k2%=mod;
    ans=ask(k1,k2);
    ans=(ans-d+mod)%mod*inv(c)%mod;
}
void work2()
{
    m2=(m2-2+mod)%(mod-1);
    k1=f_pow(a,m2)*c%mod;k2=b*c%mod*((f_pow(a,m2)-1+mod)%mod)%mod*inv(a-1)%mod+d;
    ans=ask(k1,k2);
    ans=(ans-d+mod)%mod*inv(c)%mod;
}
int main()
{
    long long l;
    scanf("%s",n);l=strlen(n);
    for (long long i=0;i<l;i++)
    {
        n1=(n1*10+n[i]-0)%mod;
        n2=(n2*10+n[i]-0)%(mod-1);
    }
    scanf("%s",m);l=strlen(m);
    for (long long i=0;i<l;i++)
    {
        m1=(m1*10+m[i]-0)%mod;
        m2=(m2*10+m[i]-0)%(mod-1);
    }
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    if (a==1) work1();
    else work2();
    printf("%lld\n",ans);
    return 0;
}

 

BZOJ 3240 矩阵游戏