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)^{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:
```cpp
#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:
```cpp
#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;
}
```