2021 牛客多校第 4 场

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$ 个错误公式。
Xi Ruoyao
Xi Ruoyao
PhD Student

Retired from ICPC, now a PhD student and an assistant ICPC coach (with no salary).