给定一个\(2n\)张卡的卡组，其中有\(n\)张强化卡（其权值为一大于\(1\)的整数），\(n\)张攻击卡（其权值为一正整数）。在一次游戏中，你需要有序的打出一些卡牌，如果说你打了一张权值为\(x\)的攻击卡，那么对对方造成\(x\)点伤害；如果说你打出了一张权值为\(x\)的强化卡，那么之后所有伤害乘上\(x\)。

现在，你需要随机从卡组中抽出\(m\)张牌，然后选出其中的\(k\)张照一定顺序打出，要求使得产生的伤害最大化。求伤害的期望，答案乘\(\binom{2n}{m}\)再膜\(998244353\)输出。

\(1\leq k\leq m\leq 2n\leq 3000, 1\leq x\leq 10^8\)（其中\(x\)为牌的权值）。

多组数据，满足\(\sum 2n\leq 30000\)。

其实那个期望就是组合了吧……就是让你求所有取出方案的最优解之和。

然后假设一种方案拿了\(a\)张强化牌和\(b\)张攻击牌。首先强化牌肯定放到最前面发动，并且我们要尽可能发动比较优的牌。然后我们发现如果\(a < k - 1\)的话那么我们打出所欲强化牌，然后再在剩下的攻击牌中择优发动；其他情况就打出最优的\(k - 1\)张强化牌，然后打出一张最强的攻击牌。

然后考虑怎么实现这个过程……我们设\(F_{i, j}\)表示选所有\(i\)张强化然后再打出其中\(j\)张的最优解之和，\(G_{i, j}\)表示攻击牌的类似意义。那么我们就枚举给强化牌安排多少张即可。至于\(F\)和\(G\)的求法，首先我们要把两个数组排序一下，可以再记状态\(f_{i, j}\)表示以\(i\)结尾（\(i\)必选）并且用了\(j\)张得所有情况的和，然后我们组合数搞一下就能求\(F\)了……\(G\)大同小异吧。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
using ll = long long;
const ll ha = 998244353LL;
const int maxn = 1505;
ll C[maxn][maxn];
void process() {
  int N = 1500;
  C[0][0] = 1;
  for(int i = 1; i <= N; i ++) {
    C[i][0] = C[i][i] = 1;
    for(int j = 1; j < i; j ++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha;
    }
  }
}

int n;
ll A[maxn], B[maxn];
ll f[maxn][maxn]; ll S[maxn];
void process_f() {
  std::fill(S, S + n + 1, 0LL);
  f[0][0] = 1; S[0] = 1;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= i; j ++) {
      f[i][j] = S[j - 1] * A[i] % ha;
    }
    for(int j = 1; j <= i; j ++) {
      S[j] = (S[j] + f[i][j]) % ha;
    }
  }
}
ll g[maxn][maxn]; ll T[maxn];
void process_g() {
  std::fill(T, T + n + 1, 0LL);
  g[0][0] = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= i; j ++) {
      g[i][j] = C[i - 1][j - 1] * B[i] % ha;
      g[i][j] = (g[i][j] + T[j - 1]) % ha;
    }
    for(int j = 1; j <= i; j ++) {
      T[j] = (T[j] + g[i][j]) % ha;
    }
  }
}
ll F(int x, int y) {
  if(x > n || x < y) return 0;
  if(x == 0) return 1;
  if(y == 0) return C[n][x];
  ll ans = 0;
  for(int i = y; i <= n; i ++) {
    ans = (ans + f[i][y] * C[n - i][x - y] % ha) % ha;
  }
  return ans;
}
ll G(int x, int y) {
  if(x > n || x < y) return 0;
  ll ans = 0;
  for(int i = y; i <= n; i ++) {
    ans = (ans + g[i][y] * C[n - i][x - y] % ha) % ha;
  }
  return ans;
}

int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int m, k; scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i ++) scanf("%lld", &A[i]);
    for(int i = 1; i <= n; i ++) scanf("%lld", &B[i]);
    std::sort(A + 1, A + 1 + n, std::greater<ll>());
    std::sort(B + 1, B + 1 + n, std::greater<ll>());
    process_f(); process_g();
    ll ans = 0;
    for(int i = 0; i <= std::min(n, m); i ++) {
      if(i < k - 1) {
        ans = (ans + F(i, i) * G(m - i, k - i) % ha) % ha;
      } else {
        ans = (ans + F(i, k - 1) * G(m - i, 1) % ha) % ha;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

• 相关文章
• 全局相关文章