B.Distance

贪心(?)

题目大意

对于两个大小相同的多重集 $\mathbb{A},\mathbb{B}\backslash mathbb\{A\},\backslash mathbb\{B\}$ ，可以选择其中任一元素 $xx$ 执行操作 $x=x+1x=x+1$ 任意次数，最少的使得 $\mathbb{A},\mathbb{B}\backslash mathbb\{A\},\backslash mathbb\{B\}$ 相同的操作次数记为 $C(\mathbb{A},\mathbb{B})C(\backslash mathbb\{A\},\backslash mathbb\{B\})$

不同大小的 $\mathbb{A},\mathbb{B}\backslash mathbb\{A\},\backslash mathbb\{B\}$ 视为 $C(\mathbb{A},\mathbb{B})=0C(\backslash mathbb\{A\},\backslash mathbb\{B\})=0$

现在，给定两个大小为 $nn$ 的多重集 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ ，求对于 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ 的所有子集 $\mathbb{A},\mathbb{B}\backslash mathbb\{A\},\backslash mathbb\{B\}$ ，最少操作次数之和 $\sum _{\mathbb{A}\subseteq \mathbb{S}}\sum _{\mathbb{B}\subseteq \mathbb{T}}C(\mathbb{A},\mathbb{B})\backslash sum\backslash limits\_\{\backslash mathbb\{A\}\; \backslash subseteq\; \backslash mathbb\{S\}\}\backslash sum\backslash limits\_\{\backslash mathbb\{B\}\; \backslash subseteq\; \backslash mathbb\{T\}\}\; C(\backslash mathbb\{A\},\backslash mathbb\{B\})$ 的值

具有相同值的两个元素视为不同元素，答案取模

解题思路

对于某对子集 $\mathbb{A},\mathbb{B}\backslash mathbb\{A\},\backslash mathbb\{B\}$ ，为了使他们相同的操作次数最少，我们会将他们排序的元素后一一对应，使每一对中较小的数变成较大的数//假设 $a_{i}a\_i$ 与 $b_{i}b\_i$ 对应，他们在这次变化中贡献的操作次数显然是 $\mathrm{\mid }{a}_i-b_i\mathrm{\mid }|a\_i-b\_i|$

那么换一种角度考虑，对于原多重集 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ ，任取一对数 $a_i,b_{j}a\_i,b\_j$ ，考虑它们俩对应的方案数 $cn{t}_{i,j}cnt\_\{i,j\}$ ，那么它们在全部方案中贡献的总操作次数即为 $\mathrm{\mid }{a}_i-b_i\mathrm{\mid }\times cn{t}_{i,j}|a\_i-b\_i|\backslash times\; cnt\_\{i,j\}$

由于我们的操作策略是排序后对应，因此先对 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ 进行排序//

选定两个数 $a_i,b_{j}a\_i,b\_j$ 后，它们在 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ 中的位置前面选 $kk$ 对数的方案数为 ${\sum }_{k=0}^{min(i-1,j-1)}{C}_{i-1}^k{C}_{j-1}^k=C_{i+j-2}^k\backslash sum\backslash limits\_\{k=0\}^\{min(i-1,j-1)\}C\_\{i-1\}^kC\_\{j-1\}^k=C\_\{i+j-2\}^k$ （范德蒙德卷积）

同理，它们在 $\mathbb{S},\mathbb{T}\backslash mathbb\{S\},\backslash mathbb\{T\}$ 中的位置后面选 $kk$ 对数的方案数为 $C_{2\ast n-i-j}^{k}C\_\{2*n-i-j\}^k$

总方案数为 $cn{t}_{i,j}=C_{i+j-2}^k{C}_{2\ast n-i-j}^{k}cnt\_\{i,j\}=C\_\{i+j-2\}^kC\_\{2*n-i-j\}^k$ ，乘以两数之差的绝对值即为它们对答案的总贡献//

预处理组合数，枚举 $i,ji,j$ 求和即可

时间复杂度

$O(n^2)O(n^2)$

参考代码

参考代码为已AC代码主干，其中部分功能需读者自行实现

#define N 2005
void solve()
{
    ll n,t;cin >> n;
    vector<ll> a(n),b(n);
    for(auto &x:a) cin >> x;
    for(auto &x:b) cin >> x;
    ll re=0;SORT(a);SORT(b);
    FORLL(i,0,n-1) FORLL(j,0,n-1)
        addto(re,mul(abs(a[i]-b[j]),mul(Get_Combination(i+j,i),Get_Combination((n-i-1)+(n-j-1),(n-i-1)))));
    cout << re << endl;
}