题解 P4967 【黑暗打击】

· · 题解

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

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

考虑推式子

如果只记录上一个的值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