+++
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}$$

前面那个东西可以最后再算，
后面和式如果没有那个<del>讨厌的</del> $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$ 个错误公式。