自动搬运

查看原文

来自洛谷，原作者为

	Hope2075 时间的流沙，淹没梦境里的夏

搬运于2025-08-24 22:05:45，当前版本为作者最后更新于2018-11-04 17:17:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

下面的题解需要参考这张图

（红色部分为有水的格子，最大的那个还没染色，可能有点小错误）

考虑推式子

如果只记录上一个的值a，会发现无法推出下一个式子

然后考虑记录其它信息

考虑把曲线横过来再灌水，（黄色部分）

这样能维护另一个序列b

然后发现可以根据a和b推出下一组a和b

$a_n=2a_{n-1}+2b_{n-1}+3\cdot 2^{n-1}-2$

$b_n=a_{n-1}+2b_{n-1}+2^{n-1}-1$

upd:时限改小，直接十进制矩阵快速幂过不了

于是我用了点奇技淫巧（

强行求通项公式

$a_n=2a_{n-1}+2b_{n-1}+3\cdot 2^{n-1}-2$

$b_n=a_{n-1}+2b_{n-1}+2^{n-1}-1$

直接相减，可以得到：

$a_n-b_n=a_{n-1}+2^{n}-1$

然后可以把$b_n$用$a_n$表示出来

$b_n=a_n-a_{n-1}-2^{n}+1$

也就是

$b_{n-1}=a_{n-1}-a_{n-2}-2^{n-1}+1$

代入以消掉$b_{n-1}$

$a_n=4a_{n-1}-2a_{n-2}+2^{n-1}$

然后变换一下

$a_n+2^n=4a_{n-1}+4\cdot 2^{n-1}-2a_{n-2}-2\cdot 2^{n-2}$

记$f_n=a_n+2^n$

则有

$f_n=4f_{n-1}-2f_{n-2}$

这时候也可以用矩阵快速幂求，但是还可以继续搞

可以用生成函数求出$f_n$，进而求出$a_n$

得到的结果：

$a_n=\frac{(2+\sqrt{2})^{n+1}}{4}+\frac{(2-\sqrt{2})^{n+1}}{4}-2^n$

这样，可以手写带$\sqrt{2}$的类来求

然而，还没有结束

如果能找到$\sqrt{2}$在模意义下的值，那么普通快速幂即可

但是这个值不一定存在

可以用欧拉判别式判断，用Cipolla算法求出值

关于这两个请自行查找资料学习

于是我就写了以下代码

#include<iostream>
using namespace std;
#define u64 unsigned long long
const u64 M=9223372036854775783LL;
u64 mup(u64 a,u64 b){
    u64 ans=0;
    while(b){
    	if(b&1){
    		ans+=a;
    		if(ans>=M)ans-=M;
    	}
    	b>>=1;
    	a+=a;
    	if(a>=M)a-=M;
    }
    return ans;
}
u64 fpow(u64 a,u64 b){
	u64 ans=1;
    while(b){
    	if(b&1)ans=mup(ans,a);
    	b>>=1;
    	a=mup(a,a);
    }
    return ans;
}
bool check(u64 num){
	return fpow(num,(M-1)/2)==1;
}
const u64 N=4*4-2;
struct qwq{
	u64 q;
	u64 r;
};
qwq operator*(qwq a,qwq b){
	qwq ans;
	ans.q=mup(a.q,b.q)+mup(mup(a.r,N),b.r);
	if(ans.q>=M)ans.q-=M;
	ans.r=mup(a.q,b.r)+mup(a.r,b.q);
	if(ans.r>=M)ans.r-=M;
	return ans;
}
qwq fpow(qwq a,u64 n){
	qwq ans=(qwq){1,0};
    while(n){
    	if(n&1)ans=ans*a;
    	n>>=1;
    	a=a*a;
    }
    return ans;
}
qwq res;
int main(){
	cout<<check(4*4-2)<<endl;
	res=fpow((qwq){4,1},(M+1)/2);
	cout<<res.q<<" "<<M-res.q<<endl;
	cout<<fpow(res.q,2uLL)<<endl;
	cout<<fpow(M-res.q,2uLL)<<endl;
	cout<<fpow(4,M-2)<<endl;
}
//5534023222971858929
//3689348813882916854

最后发现$\sqrt{2}$有这个模数意义下的值，求出了这两个值，并捎带求出了4的逆元

于是就可以做了

根据费马定理，可以在输入的时候取模进行优化

最终代码：

#include<cstdio>
#define u64 unsigned long long
const u64 M=9223372036854775783LL;
const u64 N1=5534023222971858929LL;
const u64 N2=3689348813882916854LL;
const u64 A=2305843009213693946LL;
u64 read(){
	u64 ans=0;
	u64 tmp;
	char c=getchar();
	while(c>='0'&&c<='9'){
		tmp=ans+ans;
		if(tmp>=M-1)tmp-=M-1;
		ans=tmp;
		tmp=tmp+tmp;
		if(tmp>=M-1)tmp-=M-1;
		tmp=tmp+tmp;
		if(tmp>=M-1)tmp-=M-1;
		ans=ans+tmp;
		if(ans>=M-1)ans-=M-1;
		ans=ans+c-'0';
		if(ans>=M-1)ans-=M-1;
		c=getchar();
	}
	return ans;
}
char res[25];
void write(u64 ans){
	if(ans==0){putchar('0');return;}
	int t=0;
	while(ans){res[t++]=ans%10+'0';ans/=10;}
	while(t--)putchar(res[t]);
}
u64 mup(u64 a,u64 b){
    u64 ans=0;
    while(b){
    	if(b&1){
    		ans+=a;
    		if(ans>=M)ans-=M;
    	}
    	b>>=1;
    	a+=a;
    	if(a>=M)a-=M;
    }
    return ans;
}
u64 fpow(u64 a,u64 b){
	u64 ans=1;
    while(b){
    	if(b&1)ans=mup(ans,a);
    	b>>=1;
    	a=mup(a,a);
    }
    return ans;
}
int main(){
	u64 num=read();
	u64 n1=mup(fpow(2+N1,num+1),A);
	u64 n2=mup(fpow(2+N2,num+1),A);
	u64 n3=M-fpow(2,num);
	u64 ans=n1;
	ans+=n2;
	if(ans>=M)ans-=M;
	ans+=n3;
	if(ans>=M)ans-=M;
	write(ans);
}

目前为止最优解，24ms