「CF1349F2」Slime and Sequences (Hard Version)

五月 14, 2020 · OI 题解

定义一个排列 $p$ 是好的当且仅当对于每个 $k < \max\{p\}$，存在 $1 \leq i < j \leq n$ 使得 $a_i = k-1$ 且 $a_j = k$。

定义 $f_a(k)$ 为序列 $a$ 中数值 $k$ 的出现次数，假设所有合法序列集合为 $S$，对于每个 $k \in [1;n]$，求
$\left( \sum_{a \in S} f_a(k) \right) \bmod 998244353$
$n \leq 10^5$。

题解

考虑由排列 $p$ 生成序列，在 $p_i$ 和 $p_{i+1}$ 之间填入大于或小于号，则 $a_{p_i}$ 的值为 $p_{1…i}$ 中的小于号个数 $+1$，不难验证合法序列集合和排列集合构成双射。

注意到这是个欧拉数的形式，考虑容斥维护：

$\newcommand{\strling}[2]{\left\{\begin{matrix}#1\\#2\end{matrix}\right\}} \begin{aligned} ans_i &= \sum_{m=0}^n \frac {n!} {m!} \sum_{j \ge i} (m-j)! (-1)^{j-i}\binom j i \strling m {m-j} \\ &= \sum_{j \ge i} n! (-1)^{j-i} \binom j i \sum_{m=j+1}^n \strling m {m-j} \frac {(m-j)!} {m!} \end{aligned}$

第二类斯特林数的生成函数
$\newcommand{\strling}[2]{\left\{\begin{matrix}#1\\#2\end{matrix}\right\}} \strling n k = n! [z^n] \frac {(e^z-1)^k} {k!}$

设 $h$，先带上 $m=i$ 的情况计算，最后再令 $h_0$ 减 $1$。

$\newcommand{\strling}[2]{\left\{\begin{matrix}#1\\#2\end{matrix}\right\}} \begin{aligned} h_i &= \sum_{m=i}^n \strling m {m-i} \frac{(m-i)!} {m!} \\ &= \sum_{m=i}^n [z^m] (e^z-1)^{m-i}\\ &= \sum_{j=0}^{n-i} [z^{j+i}] (e^z-1)^j \\ &= [z^i] \sum_{j=0}^{n-i} \left( \frac{e^z-1} {z} \right)^j \\ \end{aligned}$

令 $F(z) = (e^z-1)/z$，有

$\begin{aligned} h_i &= [z^i] \sum_{j=0}^{n-i} F^j(z) \\ &= [z^i] \frac{F^{n-i+1}(z)-1} {F(z)-1} \\ &= [z^i] \left( \frac{-1}{F(z)-1} + \frac{F^{n-i+1}(z)}{F(z)-1} \right) \\ \end{aligned}$

前半部分容易直接多项式求逆处理，现在考虑后半部分

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

（开始在这里卡住了，不求甚解的从题解那里拉了个式子，第二天冷静了一下，为了行文连贯，把补充理解附在后面）

设 $\omega(z) = zF(z)$，$\varphi(z)$ 满足 $\dfrac{\omega(z)}{\varphi(\omega(z))}=z$，则 $\dfrac{zF(z)}{\varphi(\omega(z))}=z$，即 $F=\varphi(\omega)$

拓展拉格朗日反演

$f,g,h$ 是 $F[[x]]$ 上的多项式，已知 $f(g(x)) = g(f(x)) = x$，则
$[x^n] h(f(x)) = \frac 1 n [x^{n-1}] h'(x) \left( \frac {x} {g(x)} \right)^n$

考虑

$\begin{aligned} f(x) &= \omega(x) \\ g(x) &= \frac x {\varphi(x)} \\ h(x) &= \frac 1 {(1-\varphi(x)) (1 - ux)} \\ \end{aligned}$

则

$\begin{aligned} & [u^{n-i+1} z^{n+1}] \frac 1 {1-\varphi (\omega(z))} \frac 1 {1-uw(z)} \\ =& [u^{n-i+1}] \frac 1 {n+1} [z^n] \left(\left(\frac 1 {1-\varphi(z)} \frac 1 {1-uz}\right)'\cdot \varphi(z)^{n+1}\right) \\ \end{aligned}$

$\displaystyle \frac 1 {(1-x)^k} = \sum_{i=0}^{\infty} \binom {i+k-1} {k-1} x^i$

直接考虑系数组合意义就可以证明。

其中

$\begin{aligned} & \left(\frac 1 {1-\varphi(z)} \frac 1 {1-uz}\right)' \\ =& \frac {\varphi'(z)} {(1-uz) (1-\varphi(z))^2} + \frac {u} {(1-\varphi(z))(1-uz)^2} \\ =& \frac {\varphi'(z)} {(1-\varphi(z))^2} \sum_{i=0}^\infty u^i z^i + \frac {1} {1 - \varphi(z)} \sum_{i=0}^\infty (i+1) u^{i+1} z^i \\ \end{aligned}$

代入到原式中有

$\begin{aligned} & \frac {[z^n] \varphi^{n+1}(z)} {n+1} \left( \frac {z^{n-i+1} \varphi'(z)} {(1-\varphi(z))^2} + \frac {(n-i+1) z^{n-i}} {1 - \varphi(z)} \right) \\ =& [z^{i-1}] \frac {\varphi^{n+1}(z) \varphi'(z)} {(n+1) (1-\varphi(z))^2} + [z^i] \frac {\varphi^{n+1}(z) (n-i+1)} {(n+1) (1-\varphi(z))} \\ \end{aligned}$

唯一的问题就是 $\varphi(x)$ 怎么求了，注意到 $\omega(x) = e^x-1$，构造得 $\dfrac z {\ln (1+z)}$。

坑

$\varphi(z) = \dfrac {z} {\ln(1+z)}$，注意到 $\ln(1+z)$ 的常数项是 $0$，不能直接求逆；
$1-\varphi(z)$ 常数项也是 $0$，同样不能直接求逆，只能求出 $(1-\varphi(z))/z$，上面的式子大概变成 $[z^{i+1}] \frac {\varphi^{n+1}(z) \varphi'(z)} {(n+1) ((1-\varphi(z))/z)^2} + [z^{i+1}] \frac {\varphi^{n+1}(z) (n-i+1)} {(n+1) ((1-\varphi(z)/z))}$
上面两种情况的处理可能带来更多的多项式长度要求。
$h_0$ 减 $1$。

补充理解

现在我们需要对 $i \in [0;n]$，求出

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

考虑用二元生成函数表示

$\begin{aligned} & [z^{n+1} u^{n-i+1}] \frac 1 {F(z)-1} \sum_{k=0}^\infty (z u F(z))^{k} \\ =& [z^{n+1} u^{n-i+1}] \frac 1 {(F(z)-1) (1-zuF(z))} \\ \end{aligned}$

如果直接对着这个式子做，是没有办法拉格朗日反演的，因为本质上我们有两个关于 $z$ 的多项式：$F(z)$ 和 $zF(z)$。我们设法构造一个关于 $F$ 的多项式使其满足 $\varphi(F(z)) = z F(z)$。

形式化的，我们想要构造多项式 $\varphi(z)$ 使得

$\varphi(F(z)) = z F(z)$

同时，由该式我们也可以直接得到 $F$ 的复合逆形式：

$\frac {\varphi(F(z))} {F(z)} = z$

说回到 $\varphi(x)$ 的构造，我们只能利用 $F(z)$ 本身的性质设法构造出 $z$：我们有

$F(z) = \frac {e^{z} - 1} {z}$

相当于有

$\ln(1 + zF(z)) = z$

不幸的是，这个式子本身还和 $z$ 有关，但启发我们改变方向，设 $\omega(z) = z F(z)$，构造多项式 $\varphi(z)$ 使得

$\begin{cases} \omega(z) = z F(z) \\ \varphi(\omega(z)) = F(z) \\ \end{cases}$

有 $\varphi(z) = \dfrac {z} {\ln(1 + z)}$，$\dfrac {\omega(z)} {\varphi(\omega(z))} = z$。即把原式转化为了：

$\frac 1 {(1 - u \omega(z)) \left(\dfrac {\omega(z)} {\ln(1 + \omega(z))}-1\right)}$

代码

#include<bits/stdc++.h>
char obuf[1<<21],*oS=obuf,*oT=oS+(1<<21)-1;
#define flush() (fwrite(obuf,1,oS-obuf,stdout),oS=obuf,void())
#define getchar() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,S,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define putchar(x) (*oS++=(x),oS==oT?flush():void())
struct Flusher_{~Flusher_(){flush();}}flusher_;
template<class T> inline void print(T x){
  if(x<0)putchar('-'),x=-x;
  if(x>9)print(x/10); putchar(x%10+'0');
}
template<class T> inline void print(T x,char c){print(x),putchar(c);}
#define love %
const int N=1e5+10,wyp=998244353;
int n,len;
struct z {
  int32_t x;
  z(int32_t x=0):x(x){}
  friend inline z operator*(z a,z b){return (int64_t)a.x*b.x love wyp;}
  friend inline z operator-(z a,z b){return (a.x-=b.x)<0?a.x+wyp:a.x;}
  friend inline z operator+(z a,z b){return (a.x+=b.x)>=wyp?a.x-wyp:a.x;}
}h[N],ans[N],inv[N],fac[N],ifac[N];
inline z fpow(z a,int b){z s=1;for(;b;b>>=1,a=a*a)if(b&1)s=s*a;return s;}
void init(int n){
  fac[0]=ifac[0]=inv[0]=inv[1]=1;
  for(int i=2;i<n;i++)inv[i]=(wyp-wyp/i)*inv[/*!!!*/wyp love i/*!!!*/];
  for(int i=1;i<n;i++)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*inv[i];
}
namespace poly{
  int len=1,rev[N<<2]; z w[N<<2];
  struct vec:std::vector<z>{
    using std::vector<z>::vector;
    inline void input(){for(size_t i=0;i<size();i++)scanf("%d",&((int&)this->operator[](i)));}
    inline void output(){for(size_t i=0;i<size();i++)printf("%d%c",this->operator[](i).x," \n"[i+1==size()]);}
    inline vec divx(){vec res=*this; return res.erase(res.begin()),res;}
    inline vec setl(size_t len){vec res=*this; return res.resize(len),res;}
    inline vec fun1(){vec res(this->begin()+1,this->end()); for(int i=0;i<res.size();i++)res[i].x=wyp-res[i].x; return res;}
  };
  int init(int n){
    int lim=1,k=0; while(lim<n)lim<<=1,++k;
    for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    for(;len<lim;len<<=1){
      z wn=fpow(3,(wyp-1)/(len<<1)); w[len]=1;
      for(int i=1;i<len;i++)w[i+len]=w[i+len-1]*wn;
    }return lim;
  }
  void dft(vec &a,int lim){
    a.resize(lim);
    for(int i=0;i<lim;i++)if(i<rev[i])std::swap(a[i],a[rev[i]]);
    for(int i=0;i<lim;i+=2){z x=a[i],y=a[i+1]*w[1];a[i]=x+y,a[i+1]=x-y;}
    for(int len=2;len<lim;len<<=1)
      for(int i=0;i<lim;i+=(len<<1))
        for(int j=0;j<len;j++){
          z x=a[i+j],y=a[i+j+len]*w[j+len];
          a[i+j]=x+y,a[i+j+len]=x-y;
        }
  }
  void idft(vec &a,int lim){
    z inv=fpow(lim,wyp-2); dft(a,lim),std::reverse(&a[1],&a[lim]);
    for(int i=0;i<lim;i++)a[i]=a[i]*inv;
  }
  vec operator+(vec a,const vec &b){
    a.resize(std::max(a.size(),b.size()));
    for(int i=0;i<b.size();i++)a[i]=a[i]+b[i]; return a;
  }
  vec operator-(vec a,const vec &b){
    a.resize(std::max(a.size(),b.size()));
    for(int i=0;i<b.size();i++)a[i]=a[i]-b[i]; return a;
  }
  vec operator*(vec a,vec b){
    if(a.size()<20||b.size()<20||(uint64_t)a.size()+b.size()<400){
      vec c(a.size()+b.size()-1);
      for(int i=0;i<a.size();i++)
        for(int j=0;j<b.size();j++)
          c[i+j]=c[i+j]+a[i]*b[j];
      return c;
    }
    int len=a.size()+b.size()-1,lim=init(len);
    dft(a,lim),dft(b,lim);
    for(int i=0;i<lim;i++)a[i]=a[i]*b[i];
    return idft(a,lim),a.resize(len),a;
  }
  vec inv(const vec &f,int len=-1){
    if((len=~len?len:f.size())==1)return vec{fpow(f[0],wyp-2)};
    vec a=inv(f,(len+1)>>1),b(&f[0],&f[len]); int lim=init((len<<1)-1);
    dft(a,lim),dft(b,lim);
    for(int i=0;i<lim;i++)a[i]=a[i]*(2-a[i]*b[i]);
    return idft(a,lim),a.resize(len),a;
  }
  vec inte(vec a){for(int i=a.size()-1;i;i--)a[i]=a[i-1]*::inv[i];return *a.begin()=0,a;}
  vec deri(vec a){for(int i=0;i<a.size()-1;i++)a[i]=a[i+1]*(i+1);return *a.rbegin()=0,a;}
  vec ln(const vec &f){return inte((deri(f)*inv(f)).setl(f.size()));}
  vec exp(const vec &f,int len=-1){
    if((len=~len?len:f.size())==1)return vec{1};
    vec a=exp(f,(len+1)>>1),b=a;b.resize(len),b=ln(b);
    for(int i=0;i<len;i++)b[i]=0-b[i]; b[0]=b[0]+1;
    for(int i=0;i<len;i++)b[i]=b[i]+f[i]; return (a*b).setl(len);
  }
  vec pow(vec a,int b){a=ln(a); for(int i=0;i<a.size();i++)a[i]=a[i]*b; return exp(a);}
}
using poly::vec;
int main(){
#ifdef memset0
  freopen("1.in","r",stdin);
#endif
  std::cin>>n;
  init(n+10),len=n+5;
  vec Finv=poly::inv(vec(ifac+1,ifac+len+1).fun1());
  for(int i=0;i<=n;i++)h[i]=Finv[i+1]; h[0]=h[0]-1;
  vec P(len); for(int i=0;i<len;i++)P[i]=(i&1?wyp-1:1)*inv[i+1]; P=poly::inv(P);
  vec Ppow=poly::pow(P,n+1);
  vec Pinv=poly::inv(P.fun1());
  vec lpart=(Ppow*Pinv).setl(len);
  vec rpart=((poly::deri(P)*Pinv).setl(len)*lpart).setl(len);
  z tmp=fpow(n+1,wyp-2);
  for(int i=0;i<=n;i++)h[i]=h[i]-tmp*(lpart[i+1]*(n-i+1)+rpart[i+1]);
  vec f(n+1),g(n+1);
  for(int i=0;i<=n;i++)f[i]=((n-i)&1?wyp-1:1)*ifac[n-i];
  for(int i=0;i<=n;i++)g[i]=fac[i]*h[i];
  f=f*g;
  for(int i=0;i<n;i++)ans[i]=f[i+n]*fac[n]*ifac[i];
  for(int i=0;i<n;i++)print(ans[i].x," \n"[i+1==n]);
}