PTA团体程序设计天梯赛 L3-033 教科书般的亵渎 （DP状压+剪枝）（30/30) (Java实现)
·
九条可怜最近在玩一款卡牌游戏。在每一局游戏中，可怜都要使用抽到的卡牌来消灭一些敌人。每一名敌人都有一个初始血量，而当血量降低到 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 教科书般的亵渎
*/
public class Main {
static final int MOD = 998244353;
static int n, K;
static int[] h;
static int[][] C;
static class Map {
long[] ks;
int[] vs;
int[] pos; // 密集存储已占用索引，使遍历达到 O(sz)
int sz, cap, mask;
Map(int c) {
cap = c; mask = c - 1;
ks = new long[c]; vs = new int[c]; pos = new int[c];
Arrays.fill(vs, -1);
}
void clear() {
// 仅清理有数据的部分，加速滚动过程
for (int i = 0; i < sz; i++) {
vs[pos[i]] = -1;
}
sz = 0;
}
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] += v;
if (vs[i] >= MOD) vs[i] -= MOD; // 减法代替取模
return;
}
i = (i + 1) & mask;
}
ks[i] = k; vs[i] = v;
pos[sz++] = i; // 记录实际存有数据的索引位置
}
}
// 剪枝函数
static boolean check(long cur, int rem, int idx) {
int cost = 0;
for (int i = idx; i <= n; i++) {
int zeroPos = Long.numberOfTrailingZeros(~cur); // 优化：直接找最右侧的 0
if (zeroPos > 50) break;
// h[i] 的原始血量如果不大于第一个缺失血量（zeroPos+1），意味着它能顺带被消灭
if (h[i] - 1 < zeroPos) continue;
cost += (h[i] - (zeroPos + 1));
if (cost > rem) return false;
cur |= (1L << zeroPos);
}
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 = 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];
if (C[i][j] >= MOD) C[i][j] -= MOD; // 加法优化
}
}
// 空间换时间
Map[] dp = new Map[K + 1];
Map[] nxt = new Map[K + 1];
for (int j = 0; j <= K; j++) {
dp[j] = new Map(1 << 15);
nxt[j] = new Map(1 << 15);
}
dp[K].put(0L, 1);
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 idx = 0; idx < m.sz; idx++) {
int j = m.pos[idx];
long curM = m.ks[j];
int ways = m.vs[j];
// 优化：处理最后一只目标的特判逻辑，剥离出内层循环
if (i == n) {
int val = curH - r; // r 必须一次性用完，cost == r
if (val >= 1) {
long nxtM = curM | (1L << (val - 1));
// 必须是全连通状态
if ((nxtM & (nxtM + 1)) == 0) {
// C[r][r] == 1，所以无需乘组合数，直接加 ways
total += ways;
if (total >= MOD) total -= MOD;
}
}
continue;
}
// 对于普通目标的转移
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;
if (!check(nxtM, nxtR, i + 1)) continue;
int add = (int) (1L * ways * C[r][cost] % MOD);
if (nxt[nxtR].sz > nxt[nxtR].cap * 0.65) rehash(nxt, nxtR);
nxt[nxtR].put(nxtM, add);
}
}
}
Map[] t = dp; dp = nxt; nxt = t;
}
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);
// rehash 也只需遍历有效项
for (int j = 0; j < old.sz; j++) {
int idx = old.pos[j];
nm.put(old.ks[idx], old.vs[idx]);
}
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社区
更多推荐
5
0- 0
已为社区贡献3条内容
所有评论(0)