感觉这题有点神的。
题意
有两种卡，分别叫攻击卡和加成卡，加成卡的效果是使每张攻击卡的效果乘上一个数，保证这个数大于一，然后攻击卡的效果是造成伤害。
每种卡一共有 \(n\) 张，然后现在会抽出 \(m\) 张卡，然后你可以使用这 \(m\) 张其中的 \(k\) 张并最大化造成的伤害之和，对于全部的局面求出造成伤害的总和。
思路
首先我们思考一个事情，就是我们是怎么使用这些卡的。
性质一：我们一定会按照从加成到攻击，从大到小的顺序来使用这些卡的，原因显然。
性质二：就是我们用的加成卡肯定不会超过 \(k - 1\) 张，并且一定能用多少用多少，直到用够 \(k -1\) 张或者用完。
首先不超过 \(k - 1\) 张是好理解的，然后为什么能用多少用多少呢？
我们假设现在造成的伤害为 \(x > 0\)，并且现在有两张卡，一张是让伤害 \(\times k, k \ge 2\)，一种是让伤害 \(+k, k \le x\)，肯定是选第一张啊，为什么第二张的效果一定小呢？因为我们是从大到小排的序，即一定会先用大的再用小的，所以第二张的效果一定小。
那我们既然已经知道解的形态之后，就可以试着 dp 了。
我们首先从大到小排一下序，然后分开 dp。
我们设 \(f_{i,j}\) 表示考虑加成卡的第 \(i\) 张，然后当前用了 \(j\) 张的系数乘积之和。
然后这个的转移是简单的，无非就是枚举当前选不选：
然后我们思考，我们设 \(x_i\) 表示加成卡选了（即在那 \(m\) 张里面） \(i\) 张的乘积之和，这个怎么得到呢？
我们发现可以钦定最后一张被用的，然后后面被选的用组合数来算，具体一点，即当我们钦定 \(i\) 是最后一张被我用的：
那么一种是当前没用够 \(k - 1\) 张，只能贡献到对应位置
一种是用够了，可以贡献到比 \(k - 1\) 大的位置，可以看看代码。
for(int i = 1; i <= n; i++){for(int j = 0; j < t; j++){f[i][j] = f[i - 1][j];if(j){int val = f[i - 1][j - 1] * a[i] % MOD;//update valif(j == t - 1){for(int k = t - 1; k <= m; k++){pre[k] += C[n - i][k - j] * val % MOD;pre[k] %= MOD;}}else{pre[j] += val;pre[j] %= MOD;}f[i][j] += val;f[i][j] %= MOD;}// f[i][j] = (f[i - 1][j - 1] * a[i] + f[i - 1][j]) % MOD;}
}
类似的，我们设 \(g_{i,j}\) 表示考虑前 \(i\) 张攻击卡，选了 \(j\) 张的总和。
然后这个记录一个对应位置的方案数也是好算的。
for(int i = 1; i <= n; i++){for(int j = 0; j <= t; j++){g[i][j] = g[i - 1][j];cnt[i][j] = cnt[i - 1][j];if(j){int val = g[i - 1][j - 1] + cnt[i - 1][j - 1] * b[i] % MOD;g[i][j] += val;g[i][j] %= MOD;cnt[i][j] += cnt[i - 1][j - 1];cnt[i][j] %= MOD;}}
}
那么怎么求出答案呢？
我们还是钦定最后一个用的，然后还是两种情况：
-
只用了一张，那么可以从 \(x_{t-1}\) 到 \(x_{m-1}\) 转移到答案，大概还得乘一个组合数。
-
用了很多张，还是只能从对应位置转移而来。
可以看看代码：
int val = g[i - 1][j - 1] + cnt[i - 1][j - 1] * b[i] % MOD;
val %= MOD;
//update ans
if(j != 1){ans += val * C[n - i][m - t] % MOD * pre[t - j] % MOD;ans %= MOD;
}
else{// assert(val == b[i]);for(int k = t - 1; k <= m - 1; k++){ans += pre[k] * val % MOD * C[n - i][m - k - 1] % MOD;ans %= MOD;}
}
那么最后也给大家总的代码。
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define uint unsigned long long
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n, m, t;
const int N = 3010, MOD = 998244353;
int a[N], b[N];
int f[N][N];
int pre[N];
int g[N][N];
int cnt[N][N];
int C[N][N];
void work(){n = read();m = read();t = read();for(int i = 1; i <= n; i++){a[i] = read();}for(int i = 1; i <= n; i++){b[i] = read();} sort(a + 1, a + 1 + n, [](int x, int y){return x > y;});sort(b + 1, b + 1 + n, [](int x, int y){return x > y;});for(int i = 0; i <= 2 * n; i++){pre[i] = 0;for(int j = 0; j <= 2 * n; j++){f[i][j] = 0;g[i][j] = 0;cnt[i][j] = 0;}}if(t == 1){int ans = 0;for(int i = 1; i <= n; i++){ans += b[i] * C[2 * n - i][m - 1] % MOD;ans %= MOD;}cout << ans << '\n';return ;}f[0][0] = 1;pre[0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j < t; j++){f[i][j] = f[i - 1][j];if(j){int val = f[i - 1][j - 1] * a[i] % MOD;//update valif(j == t - 1){for(int k = t - 1; k <= m; k++){pre[k] += C[n - i][k - j] * val % MOD;pre[k] %= MOD;}}else{pre[j] += val;pre[j] %= MOD;}f[i][j] += val;f[i][j] %= MOD;}// f[i][j] = (f[i - 1][j - 1] * a[i] + f[i - 1][j]) % MOD;}}cnt[0][0] = 1;int ans = 0;for(int i = 1; i <= n; i++){for(int j = 0; j <= t; j++){g[i][j] = g[i - 1][j];cnt[i][j] = cnt[i - 1][j];if(j){int val = g[i - 1][j - 1] + cnt[i - 1][j - 1] * b[i] % MOD;val %= MOD;//update ansif(j != 1){// cerr << "?? \n";ans += val * C[n - i][m - t] % MOD * pre[t - j] % MOD;ans %= MOD;}else{// assert(val == b[i]);for(int k = t - 1; k <= m - 1; k++){ans += pre[k] * val % MOD * C[n - i][m - k - 1] % MOD;ans %= MOD;}}// pre[j] += val;// pre[j] %= MOD;g[i][j] += val;g[i][j] %= MOD;cnt[i][j] += cnt[i - 1][j - 1];cnt[i][j] %= MOD;}// cerr << i << ' ' << j << ' ' << g[i][j] << '\n';// f[i][j] = (f[i - 1][j - 1] * a[i] + f[i - 1][j]) % MOD;}}// for(int i = 1; i <= n; i++){// for(int j = t - 1; j <= m; j++){// ans += pre[j] * b[i] * // }// }cout << ans << '\n';
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);C[0][0] = 1;for(int i = 1; i < N; i++){C[i][0] = 1;for(int j = 1; j <= i; j++){C[i][j] = C[i - 1][j - 1] + C[i - 1][j];C[i][j] %= MOD;}}int TCS = read();while(TCS --){work();}return 0;
}