题目 拜谢 @CXiii 提供题目。 NOIP 模拟赛签到题。我们有 $2^n$ 个点，编号 $0 \cdots 2^n-1$。对于一个包含 $[0, 2^n)$ 中整数的集合 $S$，我们有图 $G_S$： 当且仅当 $\exist x \in S \text{ s.t. } i \text{ xor } j = x$ 时，$i$ 与 $j$ 间有一条无向边。 对所有满足 $G_S$ 连通，且元素数量（在使得图连通的集合中）最小的 $S$ 计数。模 998244353。 初步分析与转化 使用异或的性质。$i \text{ xor } j = k \Leftrightarrow i \text{ xor } k = j$，所以，可以视为我们从一个点 $i$ 出发，每一步异或上一个 $S$ 中元素走到另一个点，重复任意多次走动而抵达终点 $j$。 考虑异或的结合律。所以这个过程整体等价于 $i$ 异或上一个常数 $k$。我们知道，$k$ 是 $S$ 中的一些元素的异或和，但又有 $k = i \text{ xor } j$。 ...
一个由不可以总司令想到的有趣概率/期望题。 题面 一套卷子上有 $n$ 道判断题。你不知道它们的答案，但是你知道存在一个常数 $p \in [0, 1]$，对任意一道题，它的答案是“正确”的概率为 $p$。 你决定采用一种策略来答题：选择一个常数 $p' \in [0, 1]$，对于任意一道题，你以 $p'$ 的概率选择“正确”。 求问： 若要使得期望做对题数最多，应该选择怎样的 $p'$？期望做对题数是多少？ 若要使得期望全对概率最大，应当选择怎样的 $p'$？期望全对概率是多大？ 解答 这是一个非常棒的问题！它涉及了期望、概率和优化策略，我们来一步步分解它。 首先，我们来明确一下变量和事件： $n$: 题目的总数。 $p$: 任意一道题的真实答案是“正确”的概率。 $1-p$: 任意一道题的真实答案是“错误”的概率。 $p'$: 你回答任意一道题为“正确”的概率。 $1-p'$: 你回答任意一道题为“错误”的概率。 你的回答策略和你不知道的真实答案是相互独立的。 1) 使得期望做对题数最多 我们要计算做对题数的期望值，并找到使这个期望值最大的 $p'$。 计算单题做对的概率 首先，我们考虑只做对一道题的概率。有两种情况可以做对一道题： 题目的真实答案是“正确”（概率为 $p$），你也回答“正确”（概率为 $p'$）。这件事情发生的概率是 $p \cdot p'$。 题目的真实答案是“错误”（概率为 $1-p$），你也回答“错误”（概率为 $1-p'$）。这件事情发生的概率是 $(1-p) \cdot (1-p')$。 由于这两种情况是互斥的，所以做对任意一道题的概率 $P(\text{单题正确})$ 是两者之和： $P(\text{单题正确}) = p p' + (1-p)(1-p')$ 计算期望做对题数 设 $X$ 为你做对的总题数。$X$ 可以看作是 $n$ 个独立的伯努利试验的和，其中每次试验“成功”（即做对题）的概率为 $P(\text{单题正确})$。 ...