不可发送单个标点符号 | 题解：P9164 「INOH」Round 1 - 狂气

Petit_Souris · 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;
}