P5162 WD与积木

题目背景

WD整日沉浸在积木中，无法自拔……

题目描述

WD想买\(n\)块积木，商场中每块积木的高度都是\(1\)，俯视图为正方形（边长不一定相同）。由于一些特殊原因，商家会给每个积木随机一个大小并标号，发给WD。

接下来WD会把相同大小的积木放在一层，并把所有层从大到小堆起来。WD希望知道所有不同的堆法中层数的期望。两种堆法不同当且仅当某个积木在两种堆法中处于不同的层中，由于WD只关心积木的相对大小，因此所有堆法等概率出现，而不是随机的大小等概率（可以看样例理解）。输出结果\(\bmod 998244353\)即可。

（如果还是不能够理解题意，请看样例）

输入输出格式

输入格式：

第一行一个数\(T\)，表示询问个数。

接下来\(T\)行每行一个数\(n\)，表示WD希望使用\(n\)块积木。

输出格式：

共\(T\)行，每行一个数表示答案\(\bmod 998244353\)。

说明

subtask1(21pts): \(1≤T≤1,000, 1≤n≤1,000\)

subtask2(37pts):\(~1\le T\le 10,~1\le n\le 100,000\)

subtask3(42pts):\(~1\le T\le 100,000,~1\le n\le 100,000\)

---

当时拿斯特林数推了一会儿没推出来就走了，原来只是部分分啊。

姿势水平屑了，今天稍微给自己普及了一些指数型生成函数。

朴素DP

\(g_n\)代表\(n\)个东西的堆法，就是有标号球和盒子不准空的方案数，就是有序贝尔数，递推的时候枚举第一堆大小。

\[ g_n=\sum_{i=1}^n \binom{n}{i}g_{n-i} \]

\(f_i\)代表\(n\)个东西所有堆法的总层数。

\[ f_n=g_n+\sum_{i=1}^n\binom{n}{i}f_{n-i} \]

从意义上看，\(f_0=0,g_0=1\)，不想从意义上看就稍微推一下。

实质还是枚举第一堆的大小，\(g_n\)算的是枚举的这一堆的贡献和，剩下的是其他堆的贡献。

然后构造指数生成函数

\[ F(x)=\sum_{i=0}^\infty\frac{f_i}{i!}x^i,G(x)=\sum_{i=0}^\infty\frac{g_i}{i!}x^i,H(x)=\sum_{i=0}^\infty\frac{1}{i!}x^i \]

然后稍微注意一下发现上面的下标是从\(1\)开始的，于是直接卷会多一个

\[ 2G=GH+1,2F=FH+G-1 \]

关于＋1-1，今天想到一种理解方式。

\(1\)实际上是一个多项式单位元，像数论卷积定义的\(\epsilon(n)=[n=1]\)那样。

然后＋1还是为了\(g_0=1\)考虑的，因为本身这个东西已经封闭了，你得给它打开一个开口啊（天呐我在扯什么

后面-1减的实际上还是\(g_0=1\)

化简一下式子

\[ F=G(G-1) \]

求逆求出\(G\)就行了

---

Code:

#include 
    
     #include 
     
      const int mod=998244353,Gi=332748118;const int M=(1<<18)+10;const int N=1e5;#define mul(a,b) (1ll*(a)*(b)%mod)#define add(a,b) ((a+b)%mod)int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}int fac[M],inv[M],ans[M],H[M],A[M],B[M],D[N],turn[M],len=1;void NTT(int *a,int typ,int len){    int L=-1;for(int i=1;i
      
       <<=1) ++L;    for(int i=1;i
       
        >1]>>1|(i&1)<
        
         >1);    for(int i=0;i
        
       
      
     
    

---

2018.12.31