Distance 2023牛客暑期多校训练营6 B

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出两个长度为n的数组a，b，每次操作可以令一个数+1，将a的一个子集A变成和b的一个子集B变成完全相同需要的最少操作数为C(A,B)，求对于a的所有子集对所有b的子集的C(A,B)的和

1<=n<=2e3

思路：我们先考察对于整个数组，如何操作使其操作数最少，首先我们需要将数字两两配对，然后分别将每一对数字变成一样的，要想整个数组求出来的最少，每一对数字之间的差就应该最小，所以最优操作就是将整个数组排序。

然后发现最大的时间复杂度是n方，显然不能枚举所有几何，但我们可以枚举每一对数字，因为根据我们上面得出的策略，在每个集合中操作的数对都是相同的，所以我们可以求每一对数组需要的操作数*含有这个数对的集合数量假设我们在长度为7的数组中选中了a[3],b[4]，那么根据范德蒙德卷积公式（acm数学（番外1） 范德蒙德卷积公式_Chmaz的博客-CSDN博客）包含他们的区间数就是C(2,2+3)*C(3,3+4)，对答案求和即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
int a[N], b[N];
ll inv[N*2], fac[N*2];
const ll MOD = 998244353;
ll qpow(ll a, ll b)
{a %= MOD;ll ret = 1;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
ll C(ll x, ll y)
{return fac[y] * inv[x] % MOD * inv[y - x] % MOD;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;fac[0] = inv[0] = 1;for (int i = 1; i <= 2 * n; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = qpow(fac[i], MOD - 2);}for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);ll ans = 0;for (ll i = 1; i <= n; i++){for (ll j = 1; j <= n; j++){ans = (ans + abs(a[i] - b[j]) * C(min(i - 1, j - 1), i-1 + j-1) % MOD * C(min(n - i, n - j), n - i + n - j) % MOD) % MOD;}}cout << ans << endl;return 0;
}