UOJ428. 【集训队作业2018】普通的计数题

http://uoj.ac/problem/428

题解

神仙题。

考虑最后一定是放了一个\(1\)，然后把其他位置都删掉了。

再考虑到对于序列中的每个位置都对应了一次操作。

我们可以对于每个放\(1\)的操作，把它这次删掉的位置对应的操作当做它的儿子节点。

这样是一个树形结构，应为最后只能剩下一个\(1\)，所以这是一个有根树。

于是我们把问题转化为了有根树计数问题。

我们先设一个\(f[i]\)表示\(i\)个节点的有根树的方案数，\(g[i]\)表示\(i\)个节点的森林的方案数(也可以只有一棵树)。

\(G\)的转移比较简单：

\[G_i=F_i+\sum_{j=1}^{i-2}\binom{i-1}{j-1}F_j*G_{i-j}
\]

转移\(F\)的话需要考虑将多棵树拼接起来。

\[F_i=\sum_{j\subset A}\binom{i-1}{j}G_{i-j-1}+[i-1\subset B]
\]

边界:\(f[1]=g[1]=0\)。

这个东西就可以分治\(FFT\)求了，注意讨论分治区间是否包含左端点。

代码

#include<bits/stdc++.h>

#define N 270009

using namespace std;

typedef long long ll;

const int mod=998244353;

const int _G=3;

const int Gi=332748118;

int rev[N],n,A,B;

ll f[N],g[N],F[N],G[N],a[N],b[N],ni[N],jie[N],fn[N];

inline void MOD(ll &x){x=x>=mod?x-mod:x;}

inline ll rd(){

    ll x=0;char c=getchar();bool f=0;

    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    return f?-x:x;

}

inline ll power(ll x,ll y){

    ll ans=1;

    while(y){

        if(y&1)ans=ans*x%mod;

        x=x*x%mod;

        y>>=1;

    }

    return ans;

}

inline void NTT(ll *a,int l,int tag){

    for(int i=1;i<l;++i)if(i>rev[i])swap(a[i],a[rev[i]]);

    for(int i=1;i<l;i<<=1){

        ll wn=power(tag?_G:Gi,(mod-1)/(i<<1));

        for(int j=0;j<l;j+=(i<<1)){

            ll w=1;

            for(int k=0;k<i;++k,w=w*wn%mod){

                ll x=a[j+k],y=a[i+j+k]*w%mod;

                MOD(a[j+k]=x+y);MOD(a[i+j+k]=x-y+mod);

            }

        }

    }

    if(!tag){

        ll ny=power(l,mod-2);

        for(int i=0;i<l;++i)a[i]=a[i]*ny%mod;

    }

}

void CDQ(int l,int r){

    if(l==r){

        if(l==1){

            f[l]=g[l]=0;

            return;

        }

        g[l]=g[l]*jie[l-1]%mod;

        f[l]=f[l]*jie[l-1]%mod;

        if(b[l-1])MOD(f[l]+=1);

        MOD(g[l]+=f[l]);

        g[l]=g[l]*ni[l]%mod;

        fn[l]=f[l]*ni[l-1]%mod;

        return;

    }

    int mid=(l+r)>>1;

    CDQ(l,mid);

    int len=1,L=0;

    while(len<=(r-l+1+mid-l+1))len<<=1,L++;

    for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1));

    for(int i=0;i<len;++i)F[i]=a[i];

    for(int i=l;i<=mid;++i)G[i-l+1]=g[i];

    NTT(F,len,1);NTT(G,len,1);

    for(int i=0;i<len;++i)F[i]=F[i]*G[i]%mod;

    NTT(F,len,0);

    for(int i=mid+1;i<=r;++i)MOD(f[i]+=F[i-l]);

    for(int i=0;i<len;++i)F[i]=G[i]=0;

    if(l==1){

       len=1;L=0;int x=(mid-l+1)*2;

       while(len<=x)len<<=1,L++;

       for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1));

       for(int i=l;i<=mid;++i)G[i-l]=g[i];

       for(int i=0;i<r-l&&i<=mid;++i)F[i]=fn[i];

       NTT(F,len,1);NTT(G,len,1);

       for(int i=0;i<len;++i)F[i]=F[i]*G[i]%mod;

       NTT(F,len,0);

       for(int i=mid+1;i<=r;++i)MOD(g[i]+=F[i-l]);

       for(int i=0;i<len;++i)F[i]=G[i]=0;

    }

    else{

       len=1;L=0;int x=mid-l+1+r-l+1;

       while(len<=x)len<<=1,L++;

       for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1));

       for(int i=l;i<=mid;++i)F[i-l]=fn[i];

       for(int i=0;i<=r-l&&i<=mid;++i)G[i]=g[i];

       NTT(F,len,1);NTT(G,len,1);

       for(int i=0;i<len;++i)F[i]=F[i]*G[i]%mod;

       NTT(F,len,0);

       for(int i=mid+1;i<=r;++i)MOD(g[i]+=F[i-l]);

       for(int i=0;i<len;++i)F[i]=G[i]=0;

       for(int i=l;i<=mid;++i)G[i-l]=g[i];

       for(int i=0;i<=r-l&&i<=mid;++i)F[i]=fn[i];

       NTT(F,len,1);NTT(G,len,1);

       for(int i=0;i<len;++i)F[i]=F[i]*G[i]%mod;

       NTT(F,len,0);

       for(int i=mid+1;i<=r;++i)MOD(g[i]+=F[i-l]);

       for(int i=0;i<len;++i)F[i]=G[i]=0;

    }

    CDQ(mid+1,r);

}

int main(){

    n=rd();A=rd();B=rd();

    jie[0]=1;

    for(int i=1;i<=n;++i)jie[i]=jie[i-1]*i%mod;

    ni[n]=power(jie[n],mod-2);

    for(int i=n-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;

    for(int i=1;i<=A;++i){int x=rd();a[x]=1;}

    for(int i=0;i<=n;++i)a[i]=a[i]*ni[i];

    for(int i=1;i<=B;++i){int x=rd();b[x]=1;}

    if(n==1){

        puts("1");

        return 0;

    }

    CDQ(1,n);

    cout<<f[n];

    return 0;

}

巴特西

UOJ428. 【集训队作业2018】普通的计数题

题解

代码

最新文章

热门文章