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
前言:记得分清小写S\(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;
}