自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

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

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

以下是正文

看起来就不是什么正常思路的 DS 题，结合模数 $998244353$，考虑生成函数。

设奇数位的生成函数为 $F(x)=a_1+a_3x+a_5x^2+\dots$，偶数位的生成函数为 $G(x)=a_2+a_4x+a_6x^2+\dots$。

那么操作 $1$ 等价于 $G\leftarrow F+G$，操作 $2$ 等价于 $F\leftarrow F+Gx$。

考虑做一个类似半在线卷积的分治 NTT：对于一个分治区间 $[l,r]$，我们可以求出，以 $(F,G)$ 作为起始值的时候，经过这个区间之后，新的二元组 $(F,G)$ 可以被表示成 $(AF+BG,CF+DG)$ 的形式，其中 $A,B,C,D$ 均为不超过 $r-l+1$ 次的多项式。

取中点 $mid$，递归计算 $[l,mid]$ 和 $[mid+1,r]$，设得到的结果为 $(AF+BG,CF+DG)$ 和 $(PF+QG,RF+SG)$，那么可以合并得到 $((PA+QC)F+(PB+QD)G,(RA+SC)F+(RB+SD)G)$。时间复杂度为 $\mathcal O(n\log^2 n)$。

除去模板的关键代码：

using namespace Poly;
ll n;
char s[N];
array<poly,4> solve(ll l,ll r){
    if(l==r){
        array<poly,4> ret;
        if(s[l]=='1'){
            ret[0].resize(1),ret[1].resize(1),ret[2].resize(1),ret[3].resize(1);
            ret[0][0]=1,ret[2][0]=1,ret[3][0]=1;
        }
        else {
            ret[0].resize(1),ret[1].resize(2),ret[2].resize(1),ret[3].resize(1);
            ret[0][0]=1,ret[1][1]=1,ret[3][0]=1;
        }
        return ret;
    }
    ll mid=(l+r)>>1;
    array<poly,4>L=solve(l,mid),R=solve(mid+1,r),ret;
    ret[0]=R[0]*L[0]+R[1]*L[2];
    ret[1]=R[0]*L[1]+R[1]*L[3];
    ret[2]=R[2]*L[0]+R[3]*L[2];
    ret[3]=R[2]*L[1]+R[3]*L[3];
    return ret;
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read();
    scanf("%s",s+1);
    array<poly,4> ret=solve(1,n);
    ll ans=1,pos=1;
    for(ll x:ret[0].a){
        if(pos>n)break;
        ans=1ll*ans*(x+1)%Mod,pos+=2;
    }
    pos=2;
    for(ll x:ret[2].a){
        if(pos>n)break;
        ans=1ll*ans*(x+1)%Mod,pos+=2;
    }
    write(ans);
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}