MX729 B
__ryp__
·
·
个人记录
我非常喜欢的组合题。
首先我们把贡献式化简：
\begin{aligned}
(\sum |A_i - B_i|)^2 &= (\sum (\max - \min))^2 \\
&= (\sum(\max + \min) - 2\sum\min)^2 \\
&= (2m - 2\sum\min)^2
\end{aligned}
这个式子拆出来之后，贡献式就变得只跟 \min 有关了。我们设 s = \sum\min，那么一个 s 的贡献就是 (2m - 2s)^2
于是我们现在就只需要知道一个 s 对应了多少个 A 与 B 序列。
首先，\min 的选法是可知的，是 n + s - 1\choose s，也就是插板。
这个时候我们已经从这两个序列中选完 n 个位置了。考虑剩下 n 个位置的选法。
剩下 n 个数的总和是 m - s，并且我们选的每个数不能小于对应位置所选的最小值。
但是我们并不知道，也不能知道每个位置上选的最小值。
我们考虑枚举有 x 个位置上，A_i 取的是最小值，这里有一个 n\choose x，现在考虑对应的 B_i 的方案，因为这里 A_i 的方案已经在前面算过了。
由于这些 B_i 至少选到最小值，我们就把最小值先选上，然后剩下 m - s 分配给 x 个数可空，方案数是 x + m - s + 1\choose m - s。
剩下的 n - x 个位置，同理，A_i 选不为最小值的任意数，且和为 m - s，方案数是显然的 m - s - 1 \choose n - x - 1。
最后的式子是
\sum\limits_{s=0}^m \sum\limits_{x=0}^n \bigg({{n \choose x}{n+s-1\choose s}{x + m - s - 1\choose m - s}{m - s - 1 \choose n -x - 1}{(2m - 2s)^2}}\bigg)