题目概述

有 $n$ 张攻击牌（造成攻击牌数值的伤害）和 $n$ 张强化牌（攻击牌伤害均 $\times$ 强化牌数值），从中抽出 $m$ 张并选出最优秀的 $K$ 张打出，求所有方案造成的伤害之和。

解题报告

容易证明能打强化牌就打强化牌，然后再打攻击牌是最优秀的（除非抽到的强化牌超过 $K$ 张，那么肯定要留一张攻击牌）。所以我们可以定义 $F(i,j)$ 为抽到了 $i$ 张攻击牌选了 $j$ 张打出的方案和，$G(i,j)$ 为抽到了 $i$ 张强化牌选了 $j$ 张打出的方案和。然后答案就是：

$$ \sum_{i=0}^{m}\begin{cases}F(m-i,K-i)G(i,i)&i\le K-1\\F(m-i,1)G(i,K-1)&i>K-1\end{cases} $$

但是 $F(x,y)$ 和 $G(x,y)$ 怎么求？对攻击牌和强化牌排序之后，我们可以强制在前 $i$ 个中选 $j$ 个，记为 $f(i,j),g(i,j)$ ，然后就可以直接组合数算出方案为 $n-i\choose x-y$ ，则 $F(x,y)=\sum f(i,j){n-i\choose x-y},G(x,y)$ 同理。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3000,MOD=998244353;

int te,n,m,K,a[maxn+5],b[maxn+5],C[maxn+5][maxn+5];
int f[maxn+5][maxn+5],g[maxn+5][maxn+5],sum[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    for (int i=C[0][0]=1;i<=n;C[i++][0]=1)
        for (int j=1;j<=i;j++) AMOD(C[i][j]=C[i-1][j-1],C[i-1][j]);
}
#define C(x,y) ((x)<(y)?0:C[x][y])
inline bool cmp(const int &A,const int &B) {return A>B;}
inline int F(int x,int y){
    int ans=0;
    for (int i=y;i<=n;i++)
        AMOD(ans,(LL)C(n-i,x-y)*f[i][y]%MOD);
    return ans;
}
inline int G(int x,int y){
    int ans=0;
    for (int i=y;i<=n;i++)
        AMOD(ans,(LL)C(n-i,x-y)*g[i][y]%MOD);
    return ans;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (Make(maxn),scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);
        for (int i=1;i<=n;i++) scanf("%d",&b[i]);sort(b+1,b+1+n,cmp);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);
        memset(sum,0,sizeof(sum));
        for (int i=1;i<=n;i++)
            for (int j=i;j;AMOD(sum[j],f[i][j]),j--)
                AMOD(f[i][j]=sum[j-1],(LL)C(i-1,j-1)*a[i]%MOD);
        memset(sum,0,sizeof(sum));g[0][0]=sum[0]=1;
        for (int i=1;i<=n;i++)
            for (int j=i;j;AMOD(sum[j],g[i][j]),j--)
                    g[i][j]=(LL)sum[j-1]*b[i]%MOD;
        for (int i=0;i<m;i++)
            if (i>K-1) AMOD(ans,(LL)F(m-i,1)*G(i,K-1)%MOD);
            else AMOD(ans,(LL)F(m-i,K-i)*G(i,i)%MOD);
        printf("%d\n",ans);ans=0;
    }
    return 0;
}