题解 P1397 【[NOI2013]矩阵游戏】

· · 题解

来一发暴力题解吧。

首先看了这道题，感觉这种递推应该要用矩阵乘法。

初始矩阵，记做A_3

1
1

然后对于每一行，有一个转移矩阵A_1

a b
0 1

对于每一列，有一个转移矩阵A_2

c d
0 1

那么转移到最后一行最后一列，就应该是A_1^{m-1}(A_2A_1^{m-1})(A_2A_1^{m-1})...A_3

也就是A_1^{m-1}(A_2A_1^{m-1})^{n-1}A_3

做到这里，我想，哇塞，这题不就是大水题了吗！可以使用十进制快速幂，这种方法就是若是求x的y次方，从低位到高位查看y十进制下的每一位，这一位为几，就让ans乘几个x，然后让x=x^10，不断这样操作即可。

然后我很高兴地写了十进制式的快速幂，忽然发现时限只有1s，又卡了一发常数，1752ms,AC。

A完后才发现这道题是数学题，我却把它写成了一个暴力题。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector")
//卡常之去掉栈保护，优化效果非常明显
#define Res register
//卡常之register，优化效果不太明显
typedef long long LL;
const int mod=1000000007;
struct node{int n,m,t[3][3];}a1,a2;
int qm(int x) {return x>=mod?x-mod:x;}//卡常之加法取模操作，优化效果非常明显
int a,b,c,d,nl,ml;char n[1000005],m[1000005];
inline node operator * (const node &a,const node &b) {
    node c; c.n=a.n,c.m=b.m;
    c.t[1][1]=qm(1LL*a.t[1][1]*b.t[1][1]%mod+1LL*a.t[1][2]*b.t[2][1]%mod);
    c.t[1][2]=qm(1LL*a.t[1][1]*b.t[1][2]%mod+1LL*a.t[1][2]*b.t[2][2]%mod);
    c.t[2][1]=qm(1LL*a.t[2][1]*b.t[1][1]%mod+1LL*a.t[2][2]*b.t[2][1]%mod);
    c.t[2][2]=qm(1LL*a.t[2][1]*b.t[1][2]%mod+1LL*a.t[2][2]*b.t[2][2]%mod);
    //卡常之循环展开，优化效果非常明显
    return c;
}
inline node ksm(node x,char *y) {//十进制快速幂
    int ll=strlen(y+1);node re;
    re.t[1][1]=re.t[2][2]=1,re.t[1][2]=re.t[2][1]=0,re.n=re.m=2;
    for(Res int i=ll;i>=1;--i) {
        node tt=x;
        if(y[i]=='9') {tt=tt*tt,tt=tt*tt,tt=tt*tt,tt=tt*x,re=re*tt;}
        else if(y[i]=='8') {tt=tt*tt,tt=tt*tt,tt=tt*tt,re=re*tt;}
        else for(Res int j=1;j<=y[i]-'0';++j) re=re*x;
        node tmp=x; x=x*x,x=x*x,x=x*x,x=x*tmp,x=x*tmp;
    }
    return re;
}
int main()
{
    scanf("%s",n+1),scanf("%s",m+1),scanf("%d%d%d%d",&a,&b,&c,&d);
    nl=strlen(n+1),ml=strlen(m+1);
    for(Res int i=nl;i>=1;--i)//n,m分别减1
        if(n[i]=='0') n[i]='9';
        else {n[i]=n[i]-1;break;}
    for(Res int i=ml;i>=1;--i)
        if(m[i]=='0') m[i]='9';
        else {m[i]=m[i]-1;break;}
    a1.n=a1.m=a2.n=a2.m=2;//用上述公式进行计算
    a1.t[1][1]=a,a1.t[1][2]=b,a1.t[2][2]=1,a1=ksm(a1,m);
    a2.t[1][1]=c,a2.t[1][2]=d,a2.t[2][2]=1;
    a2=a2*a1;a2=a1*ksm(a2,n);
    printf("%d\n",qm(a2.t[1][1]+a2.t[1][2]));
    return 0;
}