指数型生成函数.
像猎人杀那样,规定已经放满的列也可以继续被选,只是不会产生影响.
枚举 $i$ ,计算第 $i$ 列空出一个鸽笼的概率.
一个合法的操作序列需要满足 $i$ 被操作了 $a_i$ 次, 所有 $\neq i$ 的 $j$ 被操作了至少 $a_j$ 次,且最后一次操作的列为 $i$ .
若某一列被操作了 $t$ 次,就会有 $G(t)=\frac{x^t}{t!n^t}$ 的贡献.
目标函数 $F(i)$ 就是把所有列可能产生的贡献卷在一起,若 $F(i) =\sum f_i\cdot x^i$ ,则第 $i$ 列的答案就是 $\sum f_i\cdot i!$ .
具体而言,
$$
F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i} \sum_{t\ge a_j}G(t)
$$
注意到 $\sum_{t\ge 0}G(t)=e^{\frac x n}$ ,所以 $F(i)$ 可以写成
$$
F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}(e^{\frac x n}-\sum_{t=0}^{a_j-1}G(t))
$$
把 $F(i)$ 展开,会得到若干项形如 $c\cdot e^{\frac{mx}n}\cdot x^t$ 的式子,将它展开,
$$
c\cdot e^{\frac{mx}n}\cdot x^t=c\cdot x^t\cdot\sum_{s\ge 0}(\frac m n)^s\frac{x^s}{s!}\\
=c\cdot \sum_{s\ge 0}(\frac m n)^s\frac{x^{s+t}}{s!}\\
$$
考虑它对答案 $\sum f_i\cdot i!$ 的贡献,
$$
c\cdot \sum_{s\ge 0}(\frac m n)^s \frac{(s+t)!}{s!}\\
=c\cdot t!\cdot\sum_{s\ge 0}(\frac m n)^s\binom{s+t}{t}
$$
记 $h(t)=\sum_{s\ge 0}(\frac m n)^s\binom{s+t}{t}$ ,则
$$
\begin{aligned}
h(t) &= \sum_{s\ge 0}(\frac m n)^s \binom{s+t}{t}\\
&=\sum_{s\ge 0}(\frac{m}{n})^s(\binom{(s-1)+t}{t}+\binom{s+(t-1)}{t-1}) \\
&=\frac{m}{n}\cdot h(t)+h(t-1)\\
&=\frac{n}{n-m}\cdot h(t-1)
\end{aligned}
$$
边界有 $h(0)=\frac{n}{n-m}$ ,可得 $h(t)=(\frac{n}{n-m})^{t+1}$ .
如果把组合数展开成多项式,变成 $\sum s^k \cdot (\frac{m}{n})^s $ 的形式,就推不下去了.
于是可知 $c\cdot e^{\frac{mx}n}\cdot x^t$ 这一项对答案的贡献为 $c\cdot (\frac{n}{n-m})^{t+1}\cdot t!$ .
观察 $F(i)$ 的形式
$$
F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}(e^{\frac x n}-\sum_{t=0}^{a_j-1}G(t))
$$
可以发现只需要维护下面这个式子展开成 $c\cdot e^{\frac{mx}n}\cdot x^t$ 的形式,
$$
\frac{1}{n}\prod_{j=1}^n(e^{\frac x n}-\sum_{t=0}^{a_j-1}G(t))
$$
枚举 $i$ 时,将 $i$ 那一项的贡献撤去,再加入 $G(a_i-1)$ 的贡献就可以了.
可以看做是有两个容量维度的背包计数,撤掉某一项的贡献相当于撤掉某个物品,时间复杂度 $O(n^3\cdot (\max a_i)^2)$ .
实际上不去撤销,每次重新对 $n$ 个元素做一个背包, $O(n^4\cdot (\max a_i)^2)$ 也能跑过去.