Codeforces Round #641 Div1.F Slime and Sequences 中文题解

Caro23333 · 2020-04-30 00:37:03 · 题解

Slime and Sequences 中文题解

UPD:你可以在这里看到 Elegia 的题解：https://blog.csdn.net/EI_Captain/article/details/106122006

Easy Version

首先我们可以将长度为 n 的好序列和长度为 n 的排列一一对应。设一个长度为 n 的排列为 a_1,a_2,\cdots,a_n ，则在每个 a_i,a_{i+1} 之间填入大于号或小于号，则 p_{a_i} 的值即为 a_1,a_2,\cdots ,a_i 之间小于号的数量加 1 ，不难验证这是一个 S 与所有排列的集合的一个一一对应。

设 d_{i,j} 为在长度为 i+1 的排列中在 a_1,a_2,\cdots ,a_{i+1} 至少有 j 个小于号的方案数，则将每一段连续的小于号当成一段，对确定的数的集合填入这一段中只有唯一一种填法，而 d_{i,j} 中有 i-j+1 段，所以 d_{i,j} 的值即为将 n 个数分成有区别的 i-j +1 组的方案数，由第二类斯特林数的 EGF 可以知道： d_{i,j}=(i+1)![z^{i+1}](e^z-1)^{i-j+1} 。我们也可以用类似第二类斯特林数的dp求出每个 d_{i,j} 的值。

求答案时，对每个 1\leq i\leq n ，我们考虑每个位置上的贡献，即对于每个 1 到 n 的排列，找每个位置前面有 i-1 个小于号的方案数，可以列出式子：

ans_{i+1}=\sum\limits_{x=0}^{n-1}\sum\limits_{y=i}^x (-1)^{y-i} {y\choose i}d_{x,y}\frac{n!}{(x+1)!}

=\frac {n!}{i!}\sum\limits_{x=0}^{n-1}\sum\limits_{y=i}^x (-1)^{y-i}\frac{y!d_{x,y}}{(y-i)!(x+1)!}

=\frac{n!}{i!} \sum\limits_{y=i}^{n-1}\frac{(-1)^{y-i}y!}{(y-i)!}\sum\limits_{x=y}^{n-1}\frac{d_{x,y}}{(x+1)!}

=\frac {n!}{i!}\sum\limits_{y=i}^{n-1} \frac{(-1)^{y-i}y!}{(y-i)!} \sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1}

如果对每个 y 求出了 \sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1} ，即可以用一次卷积求出所有 ans_i 的值。

由于存在简单的 O(n^2) 算法来对每个 y 求出上式的值，所以如果我们用 O(n^2) 的dp求 d_{x,y} ，我们就得到了一个 O(n^2) 的做法，可以通过简单版（其他形式的dp也可以得到这个复杂度，我们在这里仅给出可以导向正解的做法）。

Hard Version

接下来考虑如何在低于 O(n^2) 的时间内求出这一系列的值。

\sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1}=\sum\limits_{x=y+1}^n[z^x](e^z-1)^{x-y}

=[z^y]\sum\limits_{x=y+1}^n(\frac{e^z-1}z)^{x-y}=[z^y]\sum\limits_{x=1}^{n-y}(\frac{e^z-1}z)^x

设 F=\frac{e^z-1}z ，现在我们想要对每个 0\leq i\leq n-1 ，求出 [z^i]\sum\limits_{k=1}^{n-i}F^k 。

[z^i]\sum\limits_{k=1}^{n-i}F^k =[z^i]\frac 1{1-F}-[z^i]\frac{F^{n-i+1}}{1-F}

我们可以用一次多项式求逆求出 [z^i]\frac 1{1-F} ，现在只需处理后面的一项。

[z^i]\frac{F^{n-i+1}}{1-F}=[z^{n+1}]\frac{(zF)^{n-i+1}}{1-F}

设 w(z)=zF(z) ，\phi (z) 满足 \frac{w(z)}{\phi (w(z))}=z ，则 \frac{zF(z)}{\phi (w(z))}=z ，即 F=\phi (w)

原式 =[z^{n+1}u^{n-i+1}]\sum\limits_{k=0}^\infty \frac{(uzF)^k}{1-F}=[z^{n+1}u^{n-i+1}] \frac 1{1-\phi (w)}\frac 1{1-uw}

由拉格朗日反演可得

=[u^{n-i+1}]\frac 1{n+1} [z^n] ((\frac 1{1-\phi z}\frac 1{1-uz})'\cdot \phi (z)^{n+1})

=\frac 1{n+1} [z^nu^{n-i+1}] (\phi (z)^{n+1}\frac{u+\phi'(z)-u\phi(z)-uz\phi'(z)}{(1-\phi (z))^2(1-uz)^2})

=\frac 1{n+1} [z^nu^{n-i+1}] (\phi(z)^{n+1}(\frac {u}{(1-\phi (z))(1-uz)^2}+\frac {\phi'(z)}{(1-\phi (z))^2(1-uz)}))

=\frac 1{n+1}[z^nu^{n-i+1}](\phi (z)^{n+1}(\frac 1{1-\phi(z)}\sum\limits_{k=0}^\infty (k+1)z^ku^{k+1}+\frac{\phi'(z)}{(1-\phi (z))^2}\sum\limits_{k=0}^\infty z^ku^k))

=\frac 1{n+1}[z^n](\phi (z)^{n+1}(\frac{(n-i+1)z^{n-i}}{1-\phi (z)}+\frac{\phi'(z)z^{n-i+1}}{(1-\phi(z))^2}))

=\frac 1{n+1}([z^i](\phi(z)^{n+1}\frac{n-i+1}{1-\phi(z)})+[z^{i-1}](\phi(z)^{n+1}\frac{\phi'(z)}{(1-\phi(z))^2}))

我们可以在 O(n\log n)\ \sim \ O(n\log ^2n) 的时间内（取决于你如何求多项式exp）求出 \phi(z)^{n+1}\frac{n-i+1}{1-\phi(z)} 和 \phi(z)^{n+1}\frac{\phi'(z)}{(1-\phi(z))^2} ，从而得出答案。

总复杂度为 O(n\log n)\ \sim\ O(n\log ^2n) 。

Problem and Tutorial by he_____he

Solution(Hard Version) by Elegia

Easy Version Code:

#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int cys=998244353;
int n;
ll fac[5005],inv[5005],d[5005][5005],ans[5005];

ll qpow(ll x,ll p){
    ll ret=1;
    for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
    return ret;
}

int main(){
    n=readint();
    d[0][0]=fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys;
    inv[n]=qpow(fac[n],cys-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
    for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) d[i][j]=(d[i-1][j-1]*(i-j+1)+d[i-1][j]*j)%cys;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i]=(ans[i]+d[j][i]*inv[j])%cys;
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]*fac[n]%cys);
    printf("\n");
    return 0;
}

Hard Version Code:

#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int cys=998244353,g=3,invg=(cys+1)/3;
int n;
ll ni[200015],fac[200015],inv[200015],tw[200005];

int mod(int x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
    ll ret=1;
    for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
    return ret;
}

vi operator+(vi a,vi b){
    vi ret(max(a.size(),b.size()));
    for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+(i<b.size()?b[i]:0));
    return ret;
}

vi operator-(vi a,vi b){
    vi ret(max(a.size(),b.size()));
    for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+cys-(i<b.size()?b[i]:0));
    return ret;
}

vi operator*(vi a,ll b){
    for(int i=0;i<a.size();i++) a[i]=1ll*a[i]*b%cys;
    return a;
}

vi operator>>(vi a,int b){
    for(int i=0;i<a.size()-b;i++) a[i]=a[i+b];
    a.resize(a.size()-b);
    return a;
}

namespace poly{
    int N,l;
    int A[1100000],B[1100000],r[1100000],pre1[20][600000],pre2[20][600000];
    void pre(){
        for(int i=1,r=0;i<(1<<19);i<<=1,r++){
            int w=1,wn=qpow(g,(cys-1)/(i<<1));
            for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre1[r][j]=w;
        }
        for(int i=1,r=0;i<(1<<19);i<<=1,r++){
            int w=1,wn=qpow(invg,(cys-1)/(i<<1));
            for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre2[r][j]=w;
        }
    }
    void ntt(int *A,int N,int f){
        for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
        for(int i=1,r=0;i<N;i<<=1,r++){
            for(int j=0;j<N;j+=(i<<1)){
                for(int k=j;k<j+i;k++){
                    int x=A[k],y=1ll*A[k+i]*(f>0?pre1[r][k-j]:pre2[r][k-j])%cys;
                    A[k]=mod(x+y); A[k+i]=mod(x+cys-y);
                }
            }
        }
        if(f<0){
            int invn=qpow(N,cys-2);
            for(int i=0;i<N;i++) A[i]=1ll*A[i]*invn%cys;
        }
    }
    void init(int t){
        N=1,l=0;
        for(;N<t;N<<=1) l++;
        for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    void getmul(){
        ntt(A,N,1); ntt(B,N,1);
        for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys;
        ntt(A,N,-1);
    }
    vi mul(vi a,vi b){
        init(a.size()+b.size());
        for(int i=0;i<N;i++) A[i]=i<a.size()?a[i]:0;
        for(int i=0;i<N;i++) B[i]=i<b.size()?b[i]:0;
        getmul();
        vi ret(a.size()+b.size()-1);
        for(int i=0;i<ret.size();i++) ret[i]=A[i];
        return ret;
    }
    vi polyinv(vi a,int l){
        if(l==1) return vi(1,qpow(a[0],cys-2));
        a.resize(l);
        vi b=polyinv(a,(l+1)/2);
        init(l<<1);
        for(int i=0;i<N;i++) A[i]=i<l?a[i]:0;
        for(int i=0;i<N;i++) B[i]=i<(l+1)/2?b[i]:0;
        ntt(A,N,1); ntt(B,N,1);
        for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys*B[i]%cys;
        ntt(A,N,-1);
        vi t=b*2;
        t.resize(l);
        for(int i=0;i<l;i++) t[i]=mod(t[i]+cys-A[i]);
        return t;
    }
    vi polydiff(vi a){
        for(int i=0;i<a.size()-1;i++) a[i]=1ll*(i+1)*a[i+1]%cys;
        a.resize(a.size()-1);
        return a;
    }
    vi polyint(vi a){
        a.resize(a.size()+1);
        for(int i=a.size()-1;i>=1;i--) a[i]=1ll*a[i-1]*ni[i]%cys;
        a[0]=0;
        return a;
    }
    vi polyln(vi a,int l){
        return polyint(mul(polydiff(a),polyinv(a,l)));
    }
    vi polyexp(vi a,int l){
        if(l==1) return vi(1,1);
        a.resize(l);
        vi b=polyexp(a,(l+1)/2);
        init(l<<1);
        vi t=mul(b,vi(1,1)-polyln(b,l)+a);
        t.resize(l);
        return t;
    }
    vi polypow(vi a,int l,int k){
        return polyexp(polyln(a,l)*k,l);
    }
}

vi getans(){
    vi f(0);
    for(int i=0;i<=n+1;i++) f.push_back(inv[i+1]);
    vi tmp=poly::mul(f,poly::polyinv((vi(1,1)-f)>>1,n+1));
    vi tw(0); tw.resize(n);
    for(int i=0;i<n;i++) tw[i]=tmp[i+1];
    vi h(0);
    h.push_back(1),h.push_back(1);
    h=poly::polyinv(poly::polyln(h,n+3)>>1,n+2);
    vi g=poly::polyinv((vi(1,1)-h)>>1,n+1);
    vi ph=poly::polypow(h,n+1,n+1);
    vi t1=poly::mul(g,ph);
    vi tmp1=poly::mul(poly::polydiff(h),ph);
    tmp1.resize(n+1);
    vi tmp2=poly::mul(g,g);
    tmp2.resize(n+1);
    vi t2=poly::mul(tmp1,tmp2);
    for(int i=0;i<n;i++) tw[i]=mod(tw[i]+cys-ni[n+1]*mod(t1[i+1]*(n-i+1)%cys+t2[i+1])%cys);
    for(int i=0;i<n;i++) tw[i]=tw[i]*fac[i]%cys;
    reverse(tw.begin(),tw.end());
    tmp.clear();
    for(int i=0;i<n;i++) tmp.push_back(i&1?cys-inv[i]:inv[i]);
    tw=poly::mul(tw,tmp);
    tw.resize(n);
    reverse(tw.begin(),tw.end());
    return tw;
}

int main(){
    poly::pre();
    n=readint();
    fac[0]=inv[0]=1;
    for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%cys;
    inv[n+5]=qpow(fac[n+5],cys-2);
    for(int i=n+4;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
    for(int i=1;i<=n+5;i++) ni[i]=inv[i]*fac[i-1]%cys;
    vi res=getans();
    for(int i=0;i<n;i++) printf("%lld ",res[i]*fac[n]%cys*inv[i]%cys);
    printf("\n");
    return 0;
}