MX1195A. 差异序列题解

Iceturky · 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} 。

代码不放了。