网站正在建设中 色,行业网站渠道选择和内容运营,网站开发前端的工作内容是什么,龙发装饰登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;给出两个长度为n的数组a#xff0c;b#xff0c;每次操作可以令一个数1#xff0c;将a的一个子集A变成和b的一个子集B变成完全相同需要的最少操作数为C(A,B)#xff0c;求对于a的所有子集对所有b的子集的C(A,B)的…登录—专业IT笔试面试备考平台_牛客网
题目大意给出两个长度为n的数组ab每次操作可以令一个数1将a的一个子集A变成和b的一个子集B变成完全相同需要的最少操作数为C(A,B)求对于a的所有子集对所有b的子集的C(A,B)的和
1n2e3
思路我们先考察对于整个数组如何操作使其操作数最少首先我们需要将数字两两配对然后分别将每一对数字变成一样的要想整个数组求出来的最少每一对数字之间的差就应该最小所以最优操作就是将整个数组排序。
然后发现最大的时间复杂度是n方显然不能枚举所有几何但我们可以枚举每一对数字因为根据我们上面得出的策略在每个集合中操作的数对都是相同的所以我们可以求每一对数组需要的操作数*含有这个数对的集合数量假设我们在长度为7的数组中选中了a[3],b[4]那么根据范德蒙德卷积公式acm数学番外1 范德蒙德卷积公式_Chmaz的博客-CSDN博客包含他们的区间数就是C(2,23)*C(3,34)对答案求和即可
//#include__msvc_all_public_headers.hpp
#includebits/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;
}
