题解：AT_wtf22_day2_d Cat Jumps

· · 题解

我能在被 GF 控制大脑的情况下做出这道巨大困难题吗？

先认为正数卡片之间是可区分的，最后除去每个数出现次数的阶乘之积即可。建立形式幂级数，用形式变元 z_1,z_2,\cdots,z_N 代表每个正数卡片，x 代表负数卡片。

设 w 表示 “从 1 开始第一次走到 0” 的生成函数，有两种选择：

  1. 使用一个 -1，对应生成函数为 x；
  2. 使用一个正数卡片 A_i，然后进行 A_i+1 次“从 1 走到 0 的过程”，由 w 的定义知这是独立的，对应生成函数为 z_iw^{A_i+1}。

因此有：

w=x+\sum_{i=1}^Nz_iw^{A_i+1}

两侧对 x 求偏导：

\begin{aligned} \dfrac{\partial w}{\partial x}&=1+\sum_{i=1}^Nz_i(A_i+1)w^{A_i}\dfrac{\partial w}{\partial x}\\ \dfrac{\partial w}{\partial x}&=\left(1-\sum_{i=1}^Nz_i(A_i+1)w^{A_i}\right)^{-1} \end{aligned}

对 x 求偏导的组合意义为标记一个 -1，考虑在标记后的 “从 1 开始第一次走到 0 的方案” 和 “任意从 0 开始最后回到 0 的方案” 间构造双射。

对于一个任意从 0 开始最后回到 0 的方案，在其末尾追加一个 -1 后得到一个总和为 -1 且所有元素 \ge-1 的序列，变形之后可以成为 Raney 定理适用的形式，恰有一个循环移位满足除最后一个位置外的前缀和均 \ge 0，对应一个从 1 走到 0 中途不经过 0 的方案（坐标均 \ge 1）；至于逆映射，直接把被标记的 -1 循环移位到末尾并删去即可，这是双射。

因此，设 c 为 “从 0 开始第一次走到 0” 的生成函数，有 \dfrac{1}{1-c}=\dfrac{\partial w}{\partial x}，也就是说：

c=\sum_{i=1}^Nz_i(A_i+1)w^{A_i}

令 U=\{1,2,\cdots,N\}，现在要提取 [z_U]c^k，将其展开：

[z_U]c^k=\sum_{|S|=k}k!\left(\prod_{i\in S}(A_i+1)\right)[z_{U\setminus S}]w^{\sum_{i\in S}A_i}

令 p=\displaystyle\sum_{i\in S}A_i，现在只需要提取 w^p 在 R=U\setminus S 中的变量系数，其它的可以设为 0，令 w_0 满足 w_0=1+\displaystyle\sum_{i\in R}z_iw_0^{A_i+1}，再令 v=w_0-1，那么有：

v=\sum_{i\in R}z_i(1+v)^{A_i+1}

令 n=|R|=N-k。为便于使用拉格朗日反演，添加形式变元 t，代换 z_i\gets tz_i（动机？可以联想子集卷积的占位元），那么：

v=\sum_{i\in R}(tz_i)(1+v)^{A_i+1}=t\sum_{i\in R}z_i(1+v)^{A_i+1}

化成 v=t\Phi(v) 的形式之后就可以拉反了，由于 |R|=n，我们要提取的是 t^n 项系数：

\begin{aligned} [t^n]H(v)&=\dfrac 1n[v^{n-1}]H'(v)\Phi(v)^n\\ [t^n](1+v)^p&=\dfrac 1n[v^{n-1}]\left(p(1+v)^{p-1}\left(\sum_{i\in R}z_i(1+v)^{A_i+1}\right)^n\right) \end{aligned}

现在要从中提取 z_R 项系数，对于里面那个东西的 n 次方，由于 |R|=n，其 z_R 系数就是 n!\displaystyle\prod_{i\in R}(1+v)^{A_i+1}=n!(1+v)^{\sum_{i\in R}(A_i+1)}。

因此有：

\begin{aligned} [z_R]w^p&=p(n-1)![v^{n-1}](1+v)^{p-1+\sum_{i\in R}(A_i+1)}\\&=p(n-1)!\dbinom{p-1+\sum_{i\in R}(A_i+1)}{n-1}\\&=p(N-k-1)!\dbinom{M+N-k-1}{N-k-1} \end{aligned}

其中 M=\displaystyle\sum_{i=1}^nA_i。代入一开始的求和式：

[z_U]c^k=k!(N-k-1)!\dbinom{M+N-k-1}{N-k-1}\sum_{|S|=k}\left(\sum_{i\in S}A_i\right)\left(\prod_{i\in S}(A_i+1)\right)

考虑右边那一堆东西。定义 B_i=A_i+1，所求即为：

\begin{aligned} \sum_{|S|=k}\left(\sum_{i\in S}B_i-k\right)\left(\prod_{i\in S}B_i\right)&=\sum_{|S|=k}\left(\sum_{i\in S}B_i\right)\left(\prod_{i\in S}B_i\right)-k\sum_{|S|=k}\prod_{i\in S}B_i \end{aligned}

定义初等对称多项式 E_k=\displaystyle\sum_{|S|=k}\prod_{i\in S}B_i，考虑每个数的贡献，易知原式等于 (M+N-k)E_k-(k+1)E_{k+1}。

最后做一点收尾工作，代回原来的式子。

\begin{aligned} \fbox{answer}&=k!(N-k-1)!\dbinom{M+N-k-1}{N-k-1}((M+N-k)E_k-(k+1)E_{k+1})\\ &=k!(N-k)!\dbinom{M+N-k}{N-k}E_k-(k+1)!(N-(k+1))!\dbinom{M+N-(k+1)}{N-(k+1)} \end{aligned}

定义 F_k=k!(N-k)!\dbinom{M+N-k}{N-k}E_k，那么答案就是 F_k-F_{k+1}，当然最后不要忘了除以每个数的出现次数的阶乘之积。

组合数可以斜向递推求，唯一的问题就是求解 E_k=[x^k]\displaystyle\prod_{i=1}^N(1+B_ix)，分治 NTT 即可，复杂度为 \mathcal O(N\log^2 N) 或者 \mathcal O\left(\dfrac{N\log^2 N}{\log\log N}\right)。

放一个 \mathcal O(N^2) 的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, p = 998244353;
int n, a[N], c[N], m, b[N], e[N], fac[N], inv[N], f[N];
int qpow(int a, int b) { int c = 1; while (b) { if (b & 1) c = (ll)c * a % p; a = (ll)a * a % p, b >>= 1; } return c; }
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], c[a[i]]++, b[i] = a[i] + 1, m = (m + a[i]) % p;
    e[0] = 1; for (int i = 1; i <= n; i++) for (int j = i; j; j--) e[j] = (e[j] + (ll)b[i] * e[j - 1]) % p;
    fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % p;
    inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = ll(p - p / i) * inv[p % i] % p;
    f[0] = 1; for (int i = 1; i < n; i++) f[i] = (ll)f[i - 1] * (m + i) % p * inv[i] % p;
    reverse(f, f + n); for (int i = n; i; i--) f[i] = (ll)f[i - 1] * fac[i] % p * fac[n - i] % p * e[i] % p;
    int iv = 1; for (int i = 0; i < N; i++) iv = (ll)iv * fac[c[i]] % p; iv = qpow(iv, p - 2);
    for (int i = 1; i <= n; i++) cout << ll(f[i] - f[i + 1] + p) * iv % p << '\n';
}

据说根据拉格朗日反演的组合观点，这个和其它题解的组合推导是本质相同的（？）

（不）建议省选就照着这么出。

:::align{center} :::