即求所有情况的最大伤害之和。容易发现应该先打强化牌，至少打一张攻击牌。同样显然的是强化牌和攻击牌都应该按从大到小的顺序打。进一步可以发现，只要还有强化牌，就应该使用（当然至少留一次攻击的机会）。
于是将强化牌和攻击牌各自从大到小排序。显然可以将其分开考虑。对强化牌，设f[i][j]为前i张牌抽到j张并打出的强化倍数之和，则显然有f[i][j]=f[i-1][j]+f[i-1][j-1]·w[i]。这样就搞定了强化牌可以打完的情况。同时设g[i]为抽i张打出k-1张的强化倍数之和，dp过程中通过f数组计算，注意避免重复。对于攻击牌也进行类似dp。然后枚举两种牌各抽了几张合并一下答案即可。注意细节。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 3010 #define P 998244353 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int T,n,m,k,a[N],b[N],f[2][N][N],g[2][N],C[N][N],h[N]; int main() { #ifndef ONLINE_JUDGE freopen("bzoj5467.in","r",stdin); freopen("bzoj5467.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif T=read(); while (T--) { n=read(),m=read(),k=read();int lim=min(k-1,n); C[0][0]=1; for (int i=1;i<=n;i++) { C[i][0]=C[i][i]=1; for (int j=1;j<n;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P; } memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(h,0,sizeof(h)); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) b[i]=read(); sort(a+1,a+n+1),reverse(a+1,a+n+1); sort(b+1,b+n+1),reverse(b+1,b+n+1); f[0][0][0]=1; for (int i=1;i<=n;i++) { f[0][i][0]=1; for (int j=1;j<=lim;j++) f[0][i][j]=(f[0][i-1][j]+1ll*f[0][i-1][j-1]*a[i])%P; if (lim==0) for (int j=0;j<=n;j++) g[0][j]=C[n][j]; else for (int j=lim;j<=n;j++) g[0][j]=(g[0][j]+1ll*f[0][i-1][lim-1]*a[i]%P*C[n-i][j-lim])%P; } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) f[1][i][j]=(f[1][i-1][j]+f[1][i-1][j-1]+1ll*b[i]*C[i-1][j-1])%P; for (int j=m-k+1;j<=n;j++) g[1][j]=(g[1][j]+(f[1][i-1][j-(m-k)-1]+1ll*b[i]*C[i-1][j-(m-k)-1])%P*C[n-i][m-k])%P; } for (int i=1;i<=min(n,m);i++) for (int j=1;j<=n;j++) h[i]=(h[i]+1ll*b[j]*C[n-j][i-1])%P; /*for (int i=0;i<=n;i++) cout<<f[0][n][i]<<' ';cout<<endl; for (int i=0;i<=n;i++) cout<<g[0][i]<<' ';cout<<endl; for (int i=0;i<=n;i++) cout<<f[1][n][i]<<' ';cout<<endl; for (int i=0;i<=n;i++) cout<<g[1][i]<<' ';cout<<endl; for (int i=0;i<=n;i++) cout<<h[i]<<' ';cout<<endl;*/ int ans=0; for (int i=max(0,m-n);i<=min(n,m);i++) if (i<=lim) ans=(ans+1ll*f[0][n][i]*g[1][m-i])%P;//抽了i张强化牌 全部出完 剩余m-i张攻击牌 选m-k张不出 else ans=(ans+1ll*g[0][i]*h[m-i])%P;//抽了i张强化牌 选lim张出 剩余m-i张攻击牌 出1张 printf("%d ",ans); } return 0; }