luogu P1397 [NOI2013]矩阵游戏

题目中那两个递推式显然可以写成矩乘的形式,然后十进制快速幂即可.这里不再赘述

只有两个递推式,我们可以考虑一波推式子,首先第一行的元素应该分别是$1,a+b,a^2+ab+b,a^3+a^2b+ab+b...a^{m-1}+b\sum_{i=0}^{m-2}a^i$

然后这样子推下去,第二行最后一个元素为$a^{2(m-1)}c+a^{m-1}bc\sum_{i=0}^{m-2}a^i+a^{m-1}d+b\sum_{i=0}^{m-2}a^i$

同理,第三行最后一个元素为$a^{3(m-1)}c^2+a^{2(m-1)}bc^2\sum_{i=0}^{m-2}a^i+a^{2(m-1)}cd+a^{m-1}bc\sum_{i=0}^{m-2}a^i+a^{m-1}d+b\sum_{i=0}^{m-2}a^i$

...

所以我们可以归纳得到$f_{n,m}$为$$a^{n(m-1)}c{n-1}+a^{{m-1}d\sum_{i=0}}{n-2}(a^{m-1}c)i+b\sum_{i=0}^{m-2}ai\sum_{j=0}^{n-1}(a{m-1}c)^j$$

然后等比数列求和公式一套就完事了

注意$a=1,c=1$的情况

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define il inline

using namespace std;

const int N=1e6+10,mod=1e9+7;

il int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int inv(int a){return fpow(a,mod-2);}

int qh(int a,int n){return a==1?n:1ll*(1-fpow(a,n)+mod)*inv(1-a+mod)%mod;}

char cc[N],ss[N];

int l1,l2,n,m,nn,mm,a,b,c,d,pa,sa,sb,sc,ans,ac;

int main()

{

    scanf("%s%s",cc+1,ss+1);

    l1=strlen(cc+1),l2=strlen(ss+1);

    a=rd()%mod,b=rd()%mod,c=rd()%mod,d=rd()%mod;

    for(int i=1;i<=l1;++i) n=(1ll*n*10+cc[i]-'0')%(mod-1),nn=(1ll*nn*10+cc[i]-'0')%mod;

    for(int i=1;i<=l2;++i) m=(1ll*m*10+ss[i]-'0')%(mod-1),mm=(1ll*mm*10+ss[i]-'0')%mod;

    pa=fpow(a,(m-1+mod-1)%(mod-1));

    sa=a>1?qh(a,m-1):mm-1;

    ac=1ll*pa*c%mod;

    sb=ac>1?qh(ac,n-1):nn-1;

    sc=ac>1?qh(ac,n):nn;

    ans=1ll*fpow(c,(n-1+mod-1)%(mod-1))*fpow(pa,n)%mod;

    if(n>1) ans=(ans+1ll*pa*sb%mod*d%mod)%mod;

    ans=(ans+1ll*sc*sa%mod*b%mod)%mod;

    printf("%d\n",ans);

    return 0;

}

巴特西

luogu P1397 [NOI2013]矩阵游戏

最新文章

热门文章