本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 21:35:37

原题Link

求所有满足 $a_i,b_i\geq0$ ，$\sum a=\sum b=m$，的 $(\sum_{i=1}^n|a_i-b_i|)^2$ 的和。

首先要放弃dp想组合。

dp状态可能也没有多优，但是想不出其他做法了。设 $g_{i,x,y}$ 表示前 $i$ 个数，两个数列的和分别为 $x$ 和 $y$ 的方案数，再设一个贡献和和贡献平方和，考虑怎么把当前数的差塞到贡献的平方和里。但这个是 $\mathrm{O(nm^4)}$ 的。

考虑组合数。

绝对值太难绷，将其转化为 $\max-\min$ 。这样贡献就是 $(\sum\max-\sum\min)^2$ 。实际上，$\sum(\max+\min)=2m$ ，用这个吧 $\max$ 给替换掉，得到贡献为 $(2m-2\sum\min)^2$ 。

这样的好处是可以通过 $\sum\min$ 的方案数来求。

方案数就要比上面简单了，首先 $\min$ 每一项都只会是 $a$ 或 $b$ 内。先不考虑其在哪里，而是统一的吧 $a$ 和 $b$ 都变成最小值，然后再在较大值上加一些数来使其和达到 $m$ 。

首先是 $\sum\min$ 在数列里的分配。设 $s=\sum\min$ 。考虑插板。方案数为 $C_{s-1+n}^{n-1}$ 。

然后考虑剩余的 $m-\sum\min$ 如何分配给 $\max$ 。首先发现不能同时分给 $a_i$ 和 $b_i$ ，因为这样会改变 $ \sum\min$ 。

那么直接枚举 $a$ 中多少位置是 $\max$ ，剩下的全都给 $b$ 即可。但是需要注意的是，如果 $a$ 中有 $\max$ 被分配了 $0$ ，$b$ 中也有，那么这是会数重的。

所以可以直接钦定 $b$ 中 $\max$ 可以分配 $0$ ，$a$ 不可就可以。

这个式子是 $\sum C_n^x\cdot C_{m-s-1}^{x-1}\cdot C_{m-s-1+n-x}^{n-x-1}$ 。

后两个中，前面那个是 $a$ 的分配方案，后面是 $b$ 的。

然后乘起来即可。$ans=\sum_{s=0}^m\sum_{x=0}^nC_{s-1+n}^{n-1}\cdot C_n^x\cdot C_{m-s-1}^{x-1}\cdot C_{m-s-1+n-x}^{n-x-1}$ 。

代码不放了。