nfls模拟赛

给定 $n,x$，对于每个 $1\le y\le n$，求出所有满足 $p_x=y$ 的排列 $p$ 有多少种本质不同的笛卡尔树，答案对 $998244353$ 取模。

$n,x\le 5\times 10^5$ 。

感觉很有难度啊，不知道为啥场上这么多人会做。

考虑填一个 $y$，本质上是限制了笛卡尔树上 $x$ 的祖先个数 $<y$，并且子树大小 $\le n-y+1$ 。

这两个限制无法独立，就非常难做。

此时非常妙的一步，考虑把所有方案放在一个矩阵里，$(i,j)$ 处表示祖先个数为 $i$，并且子树大小为 $j$ 的方案。

那么询问就是询问副对角线上每个点作为右下角，左上角矩形部分的和。

看上去还是不太好做，但是注意到副对角线右下方的部分的方案都是 $0$ 。

因此一个矩形可以由上面的一个加一行，减一列得到，因此两个限制独立，只要做单独一个限制即可。

---

先考虑第一个限制，左边选 $x$ 个祖先，右边选 $y$ 个祖先，那么左右方案组合需要乘以一个 $\dbinom{x+y}{x}$。

左边选 $x$ 个祖先，那么相当于 $x+1$ 个卡特兰数卷起来，但是如果这样做就非常难做，考虑其组合意义，把祖先看成是塞在合法括号段中间的右括号，那么问题变成前面已经填了 $x$ 个左括号的合法括号序列数，这个和卡特兰数一样的容斥一下就可以做出。

---

第二个限制，左右各选一些点放在 $x$ 的儿子里，然后考虑一下其余点的贡献。

容易发现就是点数的卡特兰数，因为 $x$ 可以找到一个位置插入。

总复杂度 $\mathcal O(n\log n)$ 。

int main() {
  int n, X;
  cin >> n >> X;

  V<mint> jie(2 * n + 5, 1), ni(2 * n + 5);
  For(i, 1, 2 * n) jie[i] = jie[i - 1] * i;
  ni[2 * n] = jie[2 * n].inv();
  Rep(i, 2 * n, 1) ni[i - 1] = ni[i] * i;
  auto C = [&](int x, int y) {
    if (x < y || y < 0) return 0_m;
    return jie[x] * ni[y] * ni[x - y];
  };

  // dep
  int T = X - 1;
  poly L(T + 1);
  For(i, 0, T) L[i] = (C(2 * T - i, T) - C(2 * T - i, T + 1)) * ni[i];
  T = n - X;
  poly R(T + 1);
  For(i, 0, T) R[i] = (C(2 * T - i, T) - C(2 * T - i, T + 1)) * ni[i];
  poly dres = L * R;
  For(i, 0, n - 1) dres[i] *= jie[i];

  // siz
  fill(all(L), 0);
  For(i, 0, X - 1) L[i] = C(2 * i, i) - C(2 * i, i - 1);
  fill(all(R), 0);
  For(i, 0, n - X) R[i] = C(2 * i, i) - C(2 * i, i - 1);
  poly sres = L * R;
  For(i, 0, n - 1) {
    int t = n - i - 1;
    sres[i] *= C(2 * t, t) - C(2 * t, t - 1);
  }

  // merge
  mint Ans = dres[0];
  cout << Ans << '\n';
  For(i, 2, n) cout << (Ans += dres[i - 1] - sres[n - i + 1]) << '\n';
}