题意
给定一个位置x，求在\(p_x\)分别取1-n的所有情况下，对应笛卡尔树不同的排列个数。
题解
先不考虑\(p_x\)，列出转移式，发现是卡特兰数。
进一步地，可以把排列对应笛卡尔树意义下的不同构数，和二叉树不同构数等价联系起来：因为对于任何一个二叉树，按照中序遍历在上面填1-n，就可以唯一确定一个排列对应的笛卡尔树。然后在二叉树上考虑问题，就会具体一些。（在本题中，将二叉树的每个点填入对应的数的位置，则是BST；而填入对应的数的值，则是小根堆;明确这点就不会造成后续考虑的混乱）
然后考虑这个限制，发现很抽象；设\(p_x=y\),则x对应的节点在二叉树上应该满足：
1.\(dep_x\le y\)
2.\(siz_x\le n-y+1\)
然后当时就对着这个限制硬推，列了个\(O(n^3)\)的DP，然后转生成函数，发现非常抽象，根本没法\(poly(log)\)搞出来。
但只要稍微冷静一下，就发现这两个限制的补集是互斥的！然后就可以分别考虑了！
1.计算\(siz_x=y,y=1……n\)
对于子树内的部分，本来是卡特兰数，但此处两个子树大小有额外的限制，所以得算两个有限长度的卡特兰数序列的卷积。
对于子树外的部分，把整个子树缩成一个点，变成计算\(n-siz+1\)个点的二叉树，且第\(x-siz_{left}\)个点是叶子的方案数。
考虑先把\(x-siz\)个点的二叉树构出来，然后插入\(x-siz_{left}\)这个点（后面的点+1，就像插入排列那样），而在BST中插入一个点（且不改变其它点的相对关系）的方式是唯一的！（反之，删掉某个特定叶子的方式显然唯一，所以是双射。）所以直接算\(C_{x-siz}\)即可。
2.计算\(dep_x=y,y=1……n\)
从二叉树或者排列的角度考虑，都可以发现两边分别是\([x^{k-k1}]C^{k1}\)和\([x^{n-k+1-k2}]C^{k2}\)，而这个东西有个结论：\([x^n]C^k=\frac{k+1}（详见）{n+k+1}C_{n+n+k}^n\)，然后把这个填进多项式，乘上组合数卷积一下就行。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<21)+5,P=998244353,G[2]={3,(P+1)/3};
void inc(int& x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
}
int sum(int x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
return x;
}
void mul(int& x,int y){
x=1ll*x*y%P;
}
int prd(int x,int y){
return 1ll*x*y%P;
}
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
int rv[N],gp[2][N],iv[N],fc[N],fv[N];
void init(int n){
fc[0]=1;
for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
fv[n-1]=fpw(fc[n-1],P-2);
for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
for(int p=0;p<2;p++){
for(int i=1;i<n;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
inline void dft(int* a,int n,int p){
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
int p=0,n=1;
while(n<m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
fill(C+m,C+n,0);
}
//C=A*B m:需要C的0~(m-1)项,m~(n-1)为空
void print(char name[],int n,int* a){
printf("%s n=%d\n",name,n);
for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
int C(int n,int m){
return 1ll*fc[n]*fv[m]%P*fv[n-m]%P;
}
int ctl(int n){
return prd(C(n+n,n),iv[n+1]);
}
int Ck(int n,int k){
return prd(prd(k+1,iv[n+k+1]),C(n+n+k,n));
}
int A[N],B[N],a[N],b[N];
int main() {
init(1<<21);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
if(i<=k) a[i]=prd(Ck(k-i,i-1),fv[i-1]);
if(i<=n-k+1) b[i]=prd(Ck(n-k+1-i,i-1),fv[i-1]);
}
//print("a",n+2,a); print("b",n+2,b);
poly_mul(n+2,a,b,A);
//print("A",n+2,A);
A[n+2]=0;
for(int i=n+1;i>=2;i--){
mul(A[i],fc[i-2]);
inc(A[i],A[i+1]);
}
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
for(int i=0;i<=n;i++){
if(i<k) a[i]=ctl(i);
if(i<n-k+1) b[i]=ctl(i);
}
poly_mul(n+2,a,b,B);
for(int siz=n;siz;siz--){
B[siz]=prd(B[siz-1],ctl(n-siz));
}
//print("B",n+1,B);
B[n+1]=0;
for(int i=n;i>=0;i--) B[i]=sum(B[i],B[i+1]);
for(int i=1;i<=n;i++){
int ans=ctl(n);
inc(ans,P-A[i+2]);
inc(ans,P-B[n-i+2]);
printf("%d\n",ans);
}
return 0;
}