luoguP1397

· · 个人记录

原题

数学方法可解

由题可知
F[1][1]=1 F[i,j]=a\times F[i][j-1]+b (j\neq 1) F[i,1]=c\times F[i-1][m]+d (i\neq 1)

由上三式可推得：

\text{1式：} F[n,m]=a\times F[n,m-1]+b=(a^{m-1})\times F[n,1]+b+a\times b+...+(a^{m-2})\times b

同时

\text{2式：}F[n,m]=(a^{m-1})\times c\times F[n-1,m]+(a^{m-1})\times d+b+a\times b+..(a^{m-2})\times b

·在草稿纸上拿条件推一下就知道了

已知公式之后，先用一点数列的简单（事实）知识处理一下

p=b\times (1+a+a^{2}+a^{3}+..+a^{m-2})=b\times (1+\frac {a\times (1-a^{m-2})}{1-a})
除法用逆元解决，a=1的情况需要特判一手

然后将花里胡哨的式子替换一下

\text {由2式得：} F[n,m]=x\times F[n-1,m]+y x=a^{m-1}\times c\space\space\space\space y=a^{m-1}\times d+p

再处理一下 F[n-1,m]

\begin{aligned} F[n-1,m]&=(x^{n-2})\times F[1,m]+(y+x\times y+...+x^{n-3}\times y)\\ &=(x^{n-2})\times(a^{m-1}+p)+(y+x\times y+...+x^{n-3}\times y)\\ \end{aligned}

用和p一样的方法处理一个q

q=y\times(1+x+x^2+x^3+...+x^{n-2})=y\times(1+\frac{x\times(1-x^{n-2})}{1-x})
得到F[n,m]
F[n,m]=x^{n-1}\times(a^{m-1}+p)+q

是不是简洁多了

最后考虑一下怎么处理n,m这两大数据

用高精铁超时

这时候就需要抬出大名鼎鼎的费马小定理！

在模数MOD为质数且gcd(a,MOD)=1的前提下（由题目数据范围，a<=1e9,MOD=1e9+7)

a^{dog}\equiv a^{dog-z}(mod\space MOD) a^z\equiv 1(mod\space MOD) a^{MOD-1}\equiv 1(mod\space MOD) z=MOD-1 a^{dog}\equiv a^{dog\space mod\space (MOD-1)}(mod\space MOD)

处理之后的n和m就缩小到1e9+7之内了，用快速幂就能求出x和a的次方

也要考虑到a和x为1的特殊情况，所以再处理一个n和m取模1e9+7备用

下面是代码：

/*#STAR DOG#*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
/*十年OI一场空，不开longlong见祖宗*/
typedef double ld;
const ll Mod=100055128505716009;
const int MOD=1e9+7;
const int DD=3e5+114;
ll re(){
    ll s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
    while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}
    return s*w;
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ans;
}
ll n,m,a,b,c,d;
ll nx,mx,p,q;
ll x,y;
string nn,mm;
int main()
{
    cin>>nn;
    int len=nn.length();
    for(int i=0;i<len;i++){
        n=(10*n+nn[i]-'0')%(MOD-1);
        nx=(10*nx+nn[i]-'0')%MOD;
    }
    n=(n-1+MOD-1)%(MOD-1);
    nx=(nx-1+MOD)%MOD;
    cin>>mm;
    len=mm.length();
    for(int i=0;i<len;i++){
        m=(10*m+mm[i]-'0')%(MOD-1);
        mx=(10*mx+mm[i]-'0')%MOD;
    }
    m=(m-1+MOD-1)%(MOD-1);
    mx=(mx-1+MOD)%MOD;
    a=re();b=re();c=re();d=re();
    ll mi=qpow(a,m);
    x=mi*c%MOD;
    if(a==1)p=mx*b%MOD;
    else{
        ll phi=qpow(a-1,MOD-2);
        p=(b*(mi-1+MOD)%MOD)*phi%MOD;
    }
    ll ni=qpow(x,n);
    y=(mi*d+p)%MOD;
    if(x==1)q=nx*y%MOD;
    else q=y*(ni-1+MOD)%MOD*qpow(x-1,MOD-2)%MOD;
    printf("%lld",(ni*(mi+p)+q)%MOD); 
    return 0;
}