有攻击牌和强化牌各 $n$ 张，强化牌可以让之后所有攻击牌攻击力乘一个大于 $1$ 的系数，攻击牌可以造成伤害
求所有“抽出 $m$ 张然后打 $k$ 张”能造成的伤害之和
$k,m,2n leq 3000$
sol：
冷静一下，发现强化牌肯定要打完，因为一张攻击力最大的攻击牌就相当于没强化的强化牌
讨论一下抽到了几张强化牌
假设抽到了 $i$ 张强化牌，$k-i$ 张攻击牌
如果 $i < k$ 直接强化全打然后攻击就完事了，如果 $i geq k$ 的话打最大的 $k-1$ 张强化和最大的一张攻击
由此可以 $dp$
设 $f_i$ 为 $i$ 张强化牌最多能扩的倍数，枚举当前抽到的强化牌 $j$，则
当 $i < k$ 时，$f_i = f_{i-1} + w_j imes f_j$
else, $f_i = f_i+f_{i-1}$
设 $g_i$ 为选了 $i$ 张攻击牌不翻倍的最大攻击力，枚举当前抽到的攻击牌 $j$，则
$g_i = g_{i-1} + C_{i-1}^{j-1} imes w_j + c$ (当 $i leq (m-k+1)$ 时 $c=0$，$i>(m-k+1)$ 时 $c=g_{i-1}$)
答案就是 $sumlimits_{i=0}^m f_i imes g_{m-i}$
第一个转移显然是按倍数从大到小排序，第二个需要把攻击力从小到大排序，
第一个转移，不管是怎么转移过来的，每张强化牌的贡献都是一样的，
第二个算每张牌贡献的时候，$c$ 标注了这张攻击牌打完之后还能不能再打别的攻击牌，如果不能打就是 $0$，能打的话要求跟他一起打的尽量大，这样转移能保证我们打的是一段尽量大的攻击牌
#include<bits/stdc++.h> #define LL long long #define rep(i,s,t) for(register int i = (s),i##end = (t); i <= i##end; ++i) #define dwn(i,s,t) for(register int i = (s),i##end = (t); i >= i##end; --i) using namespace std; const int mod = 998244353; inline int read() { int x=0,f=1;char ch; for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f; for(;isdigit(ch);ch=getchar())x=10*x+ch-'0'; return x*f; } bool cmp(int a, int b) { return a > b; } LL fac[3005], inv[3005]; int T, n, m, k, ans, f[3005], g[3005], w[3005]; LL C(int n, int m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; } int main() { fac[0] = fac[1] = inv[0] = inv[1] = 1; for (int i = 2; i <= 3000; i++) { fac[i] = fac[i - 1] * i % mod; inv[i] = ((LL)mod - mod / i) * inv[mod % i] % mod; } for (int i = 2; i <= 3000; i++) inv[i] = inv[i] * inv[i - 1] % mod; T = read(); while (T--) { n = read(), m = read(), k = read(); for (int i = 1; i <= n; i++) w[i] = read(); sort(w + 1, w + n + 1, cmp); for (int i = 1; i <= max(n, m); i++) f[i] = 0; f[0] = 1; for (int i = 1; i <= n; i++) for (int j = min(m, i); j >= 1; j--) if (j <= k - 1) f[j] = (f[j] + (LL)f[j - 1] * w[i] % mod) % mod; else f[j] = (f[j] + f[j - 1]) % mod; for (int i = 1; i <= n; i++) w[i] = read(); sort(w + 1, w + n + 1); for (int i = 0; i <= max(n, m); i++) g[i] = 0; for (int i = 1; i <= n; i++) for (int j = min(m, i); j >= 1; j--) if (j <= m - (k - 1)) g[j] = (g[j] + (LL)C(i - 1, j - 1) * w[i] % mod) % mod; else g[j] = ((g[j] + g[j - 1]) % mod + (LL)C(i - 1, j - 1) * w[i] % mod) % mod; ans = 0; for (int i = 0; i <= m; i++) ans = (ans + (LL)f[i] * g[m - i] % mod) % mod; printf("%d ", ans); } return 0; }
当然比赛不会真的这么写...老老实实用两维状态前缀和优化，考后自然要选择好一点的写法