题解

由于强化卡都是大于1的，我们分析一下就会发现，尽可能多的用强化卡，至少用一张攻击卡，一定是每组卡牌的最优选择

所以我们把攻击卡和强化卡从大到小排序

我们设\(g[i][j]\)表示前i张卡牌里选择j张强化卡，能强化的倍数之和

如果\(j <= K - 1\)

\(g[i][j] = g[i - 1][j] + g[i - 1][j - 1] * w[i]\)

否则

\(g[i][j] = g[i - 1][j] + g[i - 1][j - 1]\)

但是如果用前i张卡牌里选择j张攻击卡，能造成个攻击之和的话，由于我们选的攻击卡越多能拿的攻击卡越多，不好dp

我们用\(f[i][j]\)表示前i张卡牌用了j张攻击卡，并且用了第i张，所有方案造成的攻击和

我们计算\(h(i)\)为选了i张攻击卡牌所造成的攻击和

我们算出来选i张攻击卡能出几个攻击卡

然后枚举最后一张出的攻击卡计算即可

最后的答案就是\(\sum_{i = 1}^{m}g[N][M - i] * h(i)\)

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define enter putchar('\n')#define space putchar(' ')#define mp make_pair#define pb push_back#define fi first#define se second#define pii pair
          
           #define eps 1e-7#define MAXN 3005//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
           
            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
            
             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(); }}