PTA团体程序设计天梯赛 L3-033 教科书般的亵渎 （DP+状态压缩+剪枝）（30/30) (Java实现)
九条可怜最近在玩一款卡牌游戏。在每一局游戏中，可怜都要使用抽到的卡牌来消灭一些敌人。每一名敌人都有一个初始血量，而当血量降低到 0 及以下的时候，这名敌人就会立即被消灭并从场上消失。现在，可怜面前有 n 个敌人，其中第 i 名敌人的血量是 ai，而可怜手上只有如下两张手牌：如果场上还有敌人，等概率随机选中一个敌人并对它造成一点伤害（即血量减 1），重复 K 次。对所有敌人造成一点伤害，重复该效果
·
九条可怜最近在玩一款卡牌游戏。在每一局游戏中，可怜都要使用抽到的卡牌来消灭一些敌人。每一名敌人都有一个初始血量，而当血量降低到 0 及以下的时候，这名敌人就会立即被消灭并从场上消失。
现在，可怜面前有 n 个敌人，其中第 i 名敌人的血量是 ai，而可怜手上只有如下两张手牌：
-
如果场上还有敌人，等概率随机选中一个敌人并对它造成一点伤害（即血量减 1），重复 K 次。
-
对所有敌人造成一点伤害，重复该效果直到没有新的敌人被消灭。
下面是这两张手牌效果的一些示例：
- 假设存在两名敌人，他们的血量分别是 1,2 且 K=2。那么在可怜打出第一张手牌后，可能会发生如下情况：
- 第一轮中，两名敌人各有 0.5 的概率被选中。假设第一名敌人被选中，那么它会被造成一点伤害。这时它的血量变成了 0，因此它被消灭并消失了。
- 第二轮中，因为场上只剩下了第二名敌人，所以它一定会被选中并被造成一点伤害。这时它剩下的血量为 1。
- 同样假设存在两名敌人且血量分别为 1,2。那么在可怜打出第二张手牌后，会发生如下情况：
- 第一轮中，所有敌人被造成了一点伤害。这时第一名敌人被消灭了，因此卡牌效果会被重复一遍。
- 第二轮中，所有敌人（此时只剩下第二名敌人了）被造成了一点伤害。这时第二名敌人也被消灭了，因此卡牌效果会被再重复一遍。
- 第三轮中，所有敌人（此时没有敌人剩下了）被造成了一点伤害。因为没有新的敌人被消灭了，所以卡牌效果结束。
- 如果面对的是四名血量分别为 1,2,2,4 的敌人，那么在可怜打出第二张手牌后，只有第四名敌人还会存活，且它的剩余血量为 1。
现在，可怜先打出了第一张手牌，再打出了第二张手牌。她发现，在第一张手牌效果结束后，没有任何一名敌人被消灭，但是在第二张手牌的效果结束后，所有敌人都被消灭了。
可怜想让你计算一下这种情况发生的概率是多少。
输入格式：
第一行输入两个整数 n,K(1≤n,K≤50)，分别表示敌人的数量以及第一张卡牌效果的发动次数。
第二行输入 n 个由空格隔开的整数 ai(1≤ai≤50)，表示每个敌人的初始血量。
输出格式：
在一行中输出一个整数，表示发生概率对 998244353 取模后的结果。
具体来说，如果概率的最简分数表示为 a/b(a≥0,b≥1,gcd(a,b)=1)，那么你需要输出
a×b998244351mod998244353。
输入样例 1：
3 2
2 3 3
输出样例 1：
665496236
样例解释 1：
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：[1,3,2], [1,2,3], [2,1,3] 和 [2,3,1]。前两种发生的概率是 2/9，后两种发生的概率是 1/9。因此答案为 2/3，输出 2×3998244351mod998244353=665496236。
输入样例 2：
3 3
2 3 3
输出样例 2：
776412275
样例解释 2:
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：[1,2,2]、[2,1,2] 和 [2,2,1]。第一种发生的概率是 2/9，后两种发生的概率是 1/9。因此答案为 4/9，输出 4×9998244351mod998244353=776412275。
输入样例 3：
5 3
1 4 4 2 5
输出样例 3：
367353922
输入样例 4：
12 12
1 2 3 4 5 6 7 8 9 10 11 12
输出样例 4：
452061016
代码长度限制
16 KB
时间限制
2000 ms
内存限制
256 MB
栈限制
8192 KB
import java.util.*;
import java.io.*;
/**
* 题目：L3-033 教科书般的亵渎
* 思路：
* 1. 状态压缩 DP：利用 long 类型的位掩码 (mask) 表示 1-50 血量怪物的存在情况。
* 2. 滚动优化：按怪物序号 i 进行阶段划分，使用两个 Map 数组 (dp 和 nxt) 滚动更新。
* 3. 性能核心：
* - 剪枝：预判当前 mask 在剩余 K 次调整下，是否能补齐后续所有怪物的血量断层。
*/
public class Main {
static final int MOD = 998244353;
static int n, K;
static int[] h; // 怪物原始血量
static int[][] C; // 预处理组合数
// 线性探测高效哈希表
static class Map {
long[] ks; // keys: mask
int[] vs; // vals: ways
int sz, cap, mask;
Map(int c) {
cap = c; mask = c - 1;
ks = new long[c]; vs = new int[c];
Arrays.fill(vs, -1);
}
void clear() {
if (sz == 0) return;
Arrays.fill(vs, -1);
sz = 0;
}
// 扰动函数，将相似的 mask 散布到数组各处，避免线性探测聚簇
private int hash(long k) {
long h = k ^ (k >>> 33);
h *= 0xff51afd7ed558ccdL;
h ^= (h >>> 33);
h *= 0xc4ceb9fe1a85ec53L;
h ^= (h >>> 33);
return (int) h & mask;
}
void put(long k, int v) {
int i = hash(k);
while (vs[i] != -1) {
if (ks[i] == k) {
vs[i] = (vs[i] + v) % MOD;
return;
}
i = (i + 1) & mask;
}
ks[i] = k; vs[i] = v;
sz++;
}
}
/**
* 剪枝：模拟“亵渎”触发过程
* cur: 当前血量掩码, rem: 剩余调整次数, idx: 下一个处理的怪物序号
*/
static boolean check(long cur, int rem, int idx) {
int cost = 0;
for (int i = idx; i <= n; i++) {
// 找到当前掩码中最低位的 0 (即第一个能中断亵渎的空缺)
long gap = (cur + 1) & (~cur);
if (gap > (1L << 50)) break; // 已经连通到最大血量上限
// 如果当前怪物血量已经落在已有的 mask 中，它会被亵渎连带消灭，跳过
if ((1L << (h[i] - 1)) < gap) continue;
// 否则，必须消耗调整次数将当前怪物 h[i] 降低到空缺位置 gap 处
int target = Long.numberOfTrailingZeros(gap) + 1;
cost += (h[i] - target);
if (cost > rem) return false; // 剩余次数不足以填补此断层
cur |= gap; // 模拟填补
}
return true;
}
public static void main(String[] args) throws IOException {
FastReader fr = new FastReader(System.in);
n = fr.nextInt(); K = fr.nextInt();
h = new int[n + 1];
for (int i = 1; i <= n; i++) h[i] = fr.nextInt();
Arrays.sort(h, 1, n + 1); // 必须排序，确保按血量从小到大处理
// 预处理组合数 C(n, k)
C = new int[K + 1][K + 1];
for (int i = 0; i <= K; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
// 分层滚动 DP：dp[r] 表示剩余 r 次调整机会时的状态集合
Map[] dp = new Map[K + 1];
Map[] nxt = new Map[K + 1];
for (int j = 0; j <= K; j++) {
dp[j] = new Map(1 << 14);
nxt[j] = new Map(1 << 14);
}
dp[K].put(0L, 1); // 初始状态：掩码为空，剩余 K 次机会
int total = 0;
for (int i = 1; i <= n; i++) {
int curH = h[i];
for (int j = 0; j <= K; j++) nxt[j].clear();
for (int r = 0; r <= K; r++) {
Map m = dp[r];
if (m.sz == 0) continue;
for (int j = 0; j < m.cap; j++) {
if (m.vs[j] == -1) continue;
long curM = m.ks[j];
int ways = m.vs[j];
// 枚举对当前怪物消耗的次数 cost，使其血量变为 curH - cost
for (int cost = 0; cost <= r; cost++) {
int val = curH - cost;
if (val < 1) break;
long nxtM = curM | (1L << (val - 1));
int nxtR = r - cost;
int add = (int) (1L * ways * C[r][cost] % MOD);
if (i == n) {
// 最终状态检查：必须用完所有次数，且 mask 必须是全连通状态 (11...1)
if (nxtR == 0 && (nxtM & (nxtM + 1)) == 0) total = (total + add) % MOD;
} else {
// 剪枝判断，通过则加入下一层
if (!check(nxtM, nxtR, i + 1)) continue;
if (nxt[nxtR].sz > nxt[nxtR].cap * 0.65) rehash(nxt, nxtR);
nxt[nxtR].put(nxtM, add);
}
}
}
}
// 滚动数组交换
Map[] t = dp; dp = nxt; nxt = t;
}
// 最终结果 = 合法方案数 * (n^K 的逆元)
long inv = pow(pow(n, K), MOD - 2);
System.out.println(1L * total * inv % MOD);
}
// 哈希表自动扩容
static void rehash(Map[] maps, int i) {
Map old = maps[i];
Map nm = new Map(old.cap << 1);
for (int j = 0; j < old.cap; j++) {
if (old.vs[j] != -1) nm.put(old.ks[j], old.vs[j]);
}
maps[i] = nm;
}
static long pow(long b, long e) {
long r = 1; b %= MOD;
while (e > 0) {
if ((e & 1) == 1) r = r * b % MOD;
b = b * b % MOD; e >>= 1;
}
return r;
}
// 快读
static class FastReader {
private InputStream is;
private byte[] buf = new byte[1 << 16];
private int p, l;
FastReader(InputStream s) { is = s; }
private int read() throws IOException {
if (p == l) { p = 0; l = is.read(buf); if (l <= 0) return -1; }
return buf[p++] & 0xff;
}
int nextInt() throws IOException {
int c = read(), r = 0;
while (c >= 0 && c <= 32) c = read();
while (c > 32) { r = r * 10 + (c - '0'); c = read(); }
return r;
}
}
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
3
0- 0
已为社区贡献3条内容
所有评论(0)