2023.8.7模拟
T1
Description
Solution
Code
点击查看
T2
Description
Solution
Code
点击查看
T3
Description
Solution
Code
点击查看
T4 抽卡I([THUPC2023决赛]老hu机)
link:https://www.luogu.com.cn/problem/P9379
Description
俺のターン，ドロー！（然后对面就翻开神宣把你拍出去的神抽无效了
但是出题人玩Honkai，导致背景和yugioh毛关系没有……
一共有\(n\)种卡，每种卡的编号是一个长度为\(l\)的\(01\)串，读入十进制数\(a_i\)表示。
可以进行一次操作，有\(p_i\)的概率得知第\(i\)位的值，\(1-p_i\)的概率得不到，读入\(c_i = p_i \times 10^4\)表示。
一旦能确定是哪张卡就停止，问每一张卡确定的期望操作数。
答案对\(998244353\)取模。多测。
\(1 \leq T \leq 10, 1 \leq l \leq 15,1 \leq n \leq 2^l, 1 \leq c_i \leq 10^4, 0 \leq a_i < 2^l\)
Solution
前言：记得分清小写\(p\)下角标不同所代表的含义不同，还有大小写的\(p\)（懒，不想改了
首先关注到通过若干操作得出的已确定的位置集合\(A\)。当\(A\)可以确定目标卡片时，称\(A\)合法。
期望值经典trick是通过期望的线性性求出每个合法状态\(S\)的概率\(P_S\)，乘上停留在该状态的期望时间\(t_S\)，再全部求和。
注意到合法集\(A\)的超集也是合法的，因此无论目标串和停留时间是多少，都不影响\(P_S\)
设\(p_S\)为停留在\(S\)状态的概率，那么\(p_S = \prod\limits_{i \not\in S}(1-p_i)\)（全都不告诉你，老倒霉蛋了）。
又因为另一个经典trick，\(t_S = \sum\limits p_S^x = \frac{1}{1-p_S}\)，即操作若干次仍停留在状态\(S\)，显然收敛于\(\frac{1}{1-p_S}\)
接下来考虑从\(P_S\)到\(P_T\)的转移系数，即\(\frac{\prod_{i \in T }\prod_{i \not\in T(1-p_i)\wedge i \not\in S}p_i}{1-z_S}\)，即不在状态\(T\)的不动，在\(T\)却不在\(S\)的状态必须动。可以通过预处理转移集合\(S\)需要动元素动的概率\(f_S = \prod_{i \in S} p_i\)与转移集合\(S\)的总概率\(g_S = f_S\prod_{i \not\in S}(1-p_i)\)，这样系数就可以写成\(\frac{g_T}{f_S-g_S}\)。之后就是平平无奇的枚举超集\(dp\)，\(O(3^l)\)（当然按位处理可以做到\(O(l2^l)\)，不过不影响）。
该预处理的都处理完了，接下来就是计算答案。对于目标串\(s_i\)，设\(T_i\)表示能确定串\(s_i\)的所有合法集合\(A\)，则如前文，对于\(s_i\)的答案为\(\sum_{A \not\in T_i}P_At_A\)。
对于任意的\(A\)，它不会出现在超过\(2^{|A|}\)个集合\(T_i\)中。因此\(\sum T_i \leq 3^l\)。所以我们就可以进行容斥（补集转化：好歹用一下集合名词啊），将答案写成\(\sum_A P_At_A - \sum_{A \in T_i}P_At_A\)。所有\(A\)的\(Pt\)和可以在预处理时就求出，那么剩下的就是求\(T_i\)了。
设\(h_{S,T}\)表示位置集合为\(S\)时，状态为\(T\)的唯一串标号，如果没有值为\(0\)，有多个值为\(-1\)。初始化\(h_{U,s_i} = i\)，\(U\)表示全集，即\(\{0,1,...,l-1\}\)。\(h_S\)能够从\(h_{S \cup \{x\}}\)，\(x\)为任意一个不在\(S\)中的位置。如果\(h_{S,T} = i\)，就把s_i的答案减\(P_St_S\)。
后记：我本以为wjz已经写的很详细了，没想到他已经写的尽可能精简了。（同时谴责Bronya19C的偷懒行为
Code
点击查看
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 14348917, Mod = 998244353;
int pow3[20] = {1}, p[20];
int lowbit[MaxN], id[MaxN], rev[MaxN];
int val[1<<15|10], f[1<<15|10][16];
long long powM(long long a, int t = Mod-2) {
long long ret = 1;
while (t) {
if (t&1) ret = ret*a%Mod;
a = a*a%Mod; t >>= 1;
} return ret;
}
void init() {
int x;
for (int i = 1; i <= 15; ++i) pow3[i] = pow3[i-1]*3;
for (int i = 0; i < pow3[15]; ++i) {
lowbit[i] = -1, x = i;
for (int j = 0; j < 15; ++j, x /= 3)
if (x%3 == 2) {
lowbit[i] = j;
break;
}
if (~lowbit[i]) rev[i] = rev[i-pow3[lowbit[i]]*2]|1<<lowbit[i];
}
}
int main() {
int T, l, n;
init();
scanf("%d", &T);
while (T --) {
scanf("%d%d", &l, &n);
for (int i = 0; i < l; ++i) {
scanf("%d", &p[i]);
p[i] = p[i]*powM(10000)%Mod;
}
memset(f, 0, sizeof(f));
val[0] = 1;
int sum = 0;
for (int s = 0; s < (1<<l); ++s) {
auto update = [&]() {
for (int i = 0; i < l; ++i) {
if (s&(1<<i)) f[s][i+1] = (f[s][i+1]+f[s][i])%Mod;
else {
f[s|(1<<i)][i+1] = (f[s|(1<<i)][i+1]+1ll*f[s][i]*p[i]%Mod)%Mod;
f[s][i+1] = (f[s][i+1]+1ll*f[s][i]*(1-p[i]+Mod)%Mod)%Mod;
}
}
};
update();
if (s) val[s] = f[s][l];
else val[s] = 1;
int pp = 1;
for (int i = 0; i < l; ++i)
if ((~s)&(1<<i)) pp = 1ll*pp*(1-p[i]+Mod)%Mod;
int inv = powM(1-pp+Mod);
memset(f[s], 0, sizeof(f[s]));
f[s][0] = 1ll*val[s]*inv%Mod;
update();
val[s] = 1ll*val[s]*inv%Mod;
sum = (sum+val[s])%Mod;
}
memset(id, 0, sizeof(id));
int x, xx;
for (int i = 1; i <= n; ++i) {
scanf("%d", &xx);
x = 0;
for (int j = l; j >= 1; --j) x += pow3[j-1]*((xx&(1<<(j-1)))?1:0);
id[x] = i;
}
vector<int> ans(n+1);
for (int s = 1; s < pow3[l]; ++s) {
if (~lowbit[s]) {
int u = id[s-pow3[lowbit[s]]], v = id[s-pow3[lowbit[s]]*2];
if (u == -1 || v == -1 || (u != 0) && (v != 0)) id[s] = -1;
else id[s] = u|v;
}
if (id[s] > 0) ans[id[s]] = (ans[id[s]]+val[rev[s]^((1<<l)-1)])%Mod;
} for (int i = 1; i <= n; ++i) printf("%d\n", (sum-ans[i]+Mod)%Mod);
}
return 0;
}