+++ date = "2021-07-26T21:22:00+08:00" draft = false tags = [] title = "2021 牛客多校第 4 场" authors = ["xry111"] +++

I. Inverse Pair

题意

输入一个数组，保证里面是一个排列，选择一些数组元素给他加 $1$， 最小化操作后的逆序对数。

做法

因为是一个排列，而且只能加 $1$，增加某个数组元素时， 一定不会与它后面的元素形成新的逆序对， 只考虑与它前面元素比较时会减少逆序对就行了。

如果 $a_j = a_i + 1$ 且 $j < i$，那么我们给 $a_i$ 加 $1$ 就能减少一对逆序对，但是如果同时也给 $a_j$ 加 $1$ 就减小不了。 随便画一下会发现所有数可以连成一个二分图， 可以将每个联通分量中 (除了没连边的) 所有黑点或者白点加 $1$， 即可减少相应数目的逆序对。求一下原来的逆序对数然后搞一下就行了。

G. Product

题意

给定 $n, k, D$，求

$$\sum_{a_1 + a_2 + \cdots a_n = D, a_i \geq 0} \frac{D!}{\prod (a_i + k)!}$$

做法

这个式子就是

$$\sum_{a_1 + a_2 + \cdots a_n = D} \frac{D!}{\prod a_i !} = \sum_{\{a_i\}} \binom{D}{a_1, \cdots, a_n}$$

改了一下，而这个改之前的式子众所周知就是 $n^D$。 我们考虑怎么才能凑成这种样子。令 $b_i = a_i + k$，就成了

$$\frac{D!}{(D+nk)!} \sum_{b_1 + \cdots b_n = D + nk, b_i \geq k} \binom{D+nk}{b_1, \cdots, b_n}$$

前面那个东西可以最后再算， 后面和式如果没有那个讨厌的 $b_i \geq k$ 就是 $n^{D+nk}$， 但是有这个条件以后就得把不满足它的容斥掉。 设有 $m$ 个不满足条件的 $b_i$，它们的和是 $\Delta$，对应的容斥项是

$$(-1)^m \binom{n}{m} \sum_{b_1 + \cdots + b_{n - m} = D + nk - \Delta, \Delta = \sum_{j=1}^m c_j} \binom{D + nk}{b_1, \cdots, b_{n - m}, c_1, \cdots, c_m}$$

把 $b$ 和 $c$ 先分开，变成

$$\sum_\Delta \binom{D + nk}{\Delta} \sum{c_i < k} \binom{\Delta}{c_1, \cdots, c_m} \sum{\{b_i\}} \binom{D + nk - \Delta}{b_1, \cdots, b_{n - m}}$$

其中第一项就是个二项式系数 (但是由于出题人故意毒瘤人，不能预处理阶乘， 需要一边求和一边递推)；第三项就是 $(n - m)^{D + nk - \Delta}$； 至于第二项就是将 $\Delta$ 拆分成小于 $k$ 的 $m$ 个未必递增的非负整数之和的方案数 $f(m, \Delta)$，这个东西可以递推：

$$f(i, j) = \sum_{x < k} \binom{j}{x} f(i - 1, j - x)$$

然后就完了，答案是

$$\frac{D!}{(D+nk)!} \sum_{m=0}^{n - 1} (-1)^m \binom{n}{m} \sum_\Delta \binom{D + nk}{\Delta} f(m, \Delta) (n - m)^{D + nk - \Delta}$$

全场签完到就自闭这题，最后一分钟才过，剩下啥都没干。教训：

• 推公式不能凭感觉，要用比较严格的数学符号，不然能写出差了 $114514$ 项的公式。
• 公式不对千万不要拿着暴力结果去猜，不然能猜出 $1919810$ 个错误公式。