自动搬运

查看原文

来自洛谷，原作者为

	litble 苟……苟活者在淡红的血色中，会依稀看见微茫的希望（AFO)

搬运于2025-08-24 21:24:37，当前版本为作者最后更新于2018-02-28 17:16:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来一发暴力题解吧。

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

初始矩阵，记做$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;
}