题目分析

将每次添加的字符……看成一个节点(节点有标号)?!!

添加一个字符时删除的字符……都是它的儿子?!!

这样 0 就是叶子节点,1 就是非叶节点。任意一个添加字符的方案,构成了一种唯一的森林,而本题求的东西就变成了……这个森林只有一棵树,节点数为 $n$的方案数?!!

这什么神仙思路啊 (╯°Д°)╯︵ ┻━┻

然后设 $f(i)$表示 $i$个节点构成的树的方案数(该树根节点一定是一个字符 1),$g(i)$表示 $i$个节点构成的森林的方案数(森林里每棵树的根节点都是字符 1),$A(i)=[i \in A],B(i)=[i \in B]$,就有如下 DP 方程:

$$f(n)=\sum_{i=0}^{n-1} A(i)g(n-1-i)C_{n-1}^i + B(n-1)$$

$$g(n)=\sum_{i=1}^n f(i)g(n-i)C_{n-1}^{i-1}$$
其中 $f$的方程是考虑与根节点直接相连的叶子有几个,$g$是考虑 $1$号节点所在的那棵树的大小。

然后写成卷积的形式:

$$\frac{f(n)}{(n-1)!}=\sum_{i=0}^{n-1} \frac{g(n-1-i)}{(n-1-i)!}\frac{A(i)}{i!}+\frac{B(n-1)}{n-1}$$

$$\frac{g(n)}{n!}=\frac{1}{n}(\sum_{i=1}^n \frac{f(i)}{(i-1)!}\frac{g(n-i)}{(n-i)!})$$

发现 $f$的 DP 式中带的那个卷积其实卷出来是 $n-1$,所以将 $A(i)$整体往后平移一格,卷积式改成 $\sum_{i=1}^{n} \frac{A(i)}{(i-1)!} \frac{g(n-i)}{(n-i)!}$。

还有一点就是每次删除的子段不能为空,所以强制让 $B(0)=0$,最后全部算出来后再让 $f(1)+=1$(即只有一个字符 0 即可)

初值:$f(0)=0,g(0)=1$。

然后一个分治 NTT 即可解决,完结,撒花!

gg

……个鬼啦!

这个分治 NTT 怎么做啊!$g$的方程里又有 $f$又有 $g$的!

我花了一下午在这上面啊!

好吧,其实是这样做的。首先,分治 NTT 的时候,是递归左半边区间,用 $[l,mid]$里的值去更新 $[mid+1,r]$中的值,然后递归右半边区间嘛。

对于 $f$,用 $[l,mid]$里的 $g$(已经求出正确的值了)和前 $r-l+1$项 $A$去卷积,加到右半边的 $f$中。

对于 $g$,用 $[l,mid]$里的 $f$(已经求出正确的值了)和前 $r-l+1$项 $g$去卷积,加到右半边的 $g$中。但是有一个问题,若 $l=1$,可能出现前 $r-l+1$项 $g$还没有完全算出的情况。

设 $i+j=k$,$j>mid$,$i \leq mid$,那么此时我们漏算了 $f(i)g(j)$对 $g(k)$的贡献。

不过没关系,当我们递归到一个左半边包含 $j$的 $[l,r]$(此时 $l \not= 1$)时,我们再用 $[l,mid]$里的 $g$和前 $r-l+1$项 $f$去卷积,加到右半边的 $g$中即可。

所以当 $l \not=1$时,要额外多卷积一次。

另外,注意不要不小心使用在本次卷积算贡献时,用被更新了的 $f$和 $g$去卷。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=998244353,N=262150;
int n,ma,mb,ans;
int fac[N],inv[N],ifac[N],A[N],B[N],f[N],g[N],rev[N];
int k1[N],k2[N],k3[N],k4[N];

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void NTT(int *a,int n,int x) {
    for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        int gn=ksm(3,(mod-1)/(i<<1));
        for(RI j=0;j<n;j+=(i<<1)) {
            int t1,t2,g=1;
            for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
                t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
                a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
            }
        }
    }
    if(x==1) return;
    reverse(a+1,a+n);int invn=ksm(n,mod-2);
    for(RI i=0;i<n;++i) a[i]=1LL*a[i]*invn%mod;
}

void prework() {
    fac[0]=1;for(RI i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
    inv[0]=inv[1]=1,ifac[0]=1;
    for(RI i=2;i<=n;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(RI i=1;i<=n;++i) ifac[i]=1LL*ifac[i-1]*inv[i]%mod;
}
void work(int l,int r) {
    int mid=(l+r)>>1,n=r-l+1,kn=1,len=0;
    while(kn<(n<<1)) kn<<=1,++len;
    for(RI i=0;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
    {   for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=g[i];
        for(RI i=1;i<=n;++i) k2[i]=1LL*A[i]*ifac[i-1]%mod;
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) f[i]=qm(f[i]+k1[i-l]);
    }
    {   for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=f[i];
        for(RI i=0;i<=n;++i) k2[i]=g[i];
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) g[i]=qm(g[i]+k1[i-l]);
    }
    if(l>1) {
        for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=g[i];
        for(RI i=0;i<=n;++i) k2[i]=f[i];
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) g[i]=qm(g[i]+k1[i-l]);
    }
}
void cdq(int l,int r) {
    if(l==r) {
        f[l]=qm(f[l]+1LL*B[l-1]*ifac[l-1]%mod);
        g[l]=1LL*qm(g[l]+f[l])*inv[l]%mod;
        return;
    }
    int mid=(l+r)>>1;cdq(l,mid),work(l,r),cdq(mid+1,r);
}
int main()
{
    n=read(),ma=read(),mb=read();
    for(RI i=1;i<=ma;++i) A[read()+1]=1;
    for(RI i=1;i<=mb;++i) B[read()]=1;
    prework();
    B[0]=0,g[0]=1,cdq(1,n),ans=1LL*f[n]*fac[n-1]%mod;
    if(n==1) ans=qm(ans+1);
    printf("%d\n",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注