【LOJ】#2538. 「PKUWC2018」Slay the Spire

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#define enter putchar(‘\n‘)
#define space putchar(‘ ‘)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define eps 1e-7
#define MAXN 3005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < ‘0‘ || c > ‘9‘) {
    if(c == ‘-‘) f = -1;
    c = getchar();
    }
    while(c >= ‘0‘ && c <= ‘9‘) {
    res = res * 10 + c - ‘0‘;
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar(‘-‘);x = -x;}
    if(x >= 10) {
    out(x / 10);
    }
    putchar(‘0‘ + x % 10);
}

const int MOD = 998244353;
int T;
int N,M,K,fac[MAXN],invfac[MAXN],inv[MAXN],w[2][MAXN];
int g[1505][1505],f[1505][1505],h[1505],sum[1505];
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int C(int n,int m) {
    if(n < m) return 0;
    return mul(mul(fac[n],invfac[m]),invfac[n - m]);
}
bool cmp(int a,int b) {
    return a > b;
}
void Solve() {
    read(N);read(M);read(K);
    for(int i = 1 ; i <= N ; ++i) read(w[1][i]);
    for(int i = 1 ; i <= N ; ++i) read(w[0][i]);
    sort(w[0] + 1,w[0] + N + 1,cmp);
    sort(w[1] + 1,w[1] + N + 1,cmp);
    f[0][0] = 0,g[0][0] = 1;
    memset(sum,0,sizeof(sum));
    memset(h,0,sizeof(h));
    for(int i = 1 ; i <= N ; ++i) {
    int t = min(i,M);
    f[i][0] = f[i - 1][0],g[i][0] = g[i - 1][0];
    for(int j = 1 ; j <= t ; ++j) {
        f[i][j] = inc(sum[j - 1],mul(C(i - 1,j - 1),w[0][i]));
        g[i][j] = g[i - 1][j];
        if(K - 1 >= j) g[i][j] = inc(g[i][j],mul(g[i - 1][j - 1],w[1][i]));
        else g[i][j] = inc(g[i][j],g[i - 1][j - 1]);
    }
    for(int j = 1 ; j <= t ; ++j) sum[j] = inc(sum[j],f[i][j]);
    }
    for(int c = 1 ; c <= N ; ++c) {
    if(c> M) break;
    int ch = K - min(K - 1,M - c);
    for(int i = 1 ; i <= N ; ++i) {
        h[c] = inc(h[c],mul(f[i][ch],C(N - i,c - ch)));
    }
    }
    int ans = 0;
    for(int i = 1 ; i <= M ; ++i) {
    if(i > N) break;
    if(M - i > N) continue;
    ans = inc(ans,mul(h[i],g[N][M - i]));
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    inv[1] = 1;
    for(int i = 2 ; i <= 3000 ; ++i) {
    inv[i] = mul(inv[MOD % i],MOD - MOD / i);
    }
    fac[0] = 1,invfac[0] = 1;
    for(int i = 1 ; i <= 3000 ; ++i) {
    fac[i] = mul(fac[i - 1],i);
    invfac[i] = mul(invfac[i - 1],inv[i]);
    }
    read(T);
    while(T--) {
    Solve();
    }
}