1121研讨

__staring__ · 2024-11-13 18:07:05 · 个人记录

U124681

考虑这样一个暴力，每次询问 (u,v) 时，把与 u 相连的点打上标记，枚举与 v 相邻的点检查是否有标记，复杂度 O(qm)

稍稍优化：将询问离线，并令 \deg u\ge\deg v ，将所有 u 相同的询问一起处理，v 也相同的询问直接跳过，再进行上述暴力，复杂度 O(m\sqrt q)

复杂度证明：

对于打标记的点，每个点只会进行一次打标机的操作，复杂度 O(\sum \deg u)=O(m)

对于扫标记的点，将所有点按 \deg 从大到小排序，记度数第 i 大的点度数为 d_i，作为 v 扫标记的次数为 a_i

那么这部分的复杂度 T\le\sum_{i=1}^na_id_i

显然询问度数大的点 T 上界越大，那么我们取前 \sqrt q 个点，且因为判掉了相同询问，每个点只会被其前的点作为 v ，即 a_i\le i-1，那么 T\le\sum_{i=1}^{\sqrt q}id_i

因为 i\le \sqrt q,d_i\le \frac mi ，所以 id_i\le m ，即 T\le \sum_{i=1}^{\sqrt q}id_i\le m\sqrt q

所以总复杂度为 O(m\sqrt q) ，且因为经过多次放缩，实际常数较小

BV1TSmhYZEdL 如何把魔方当作计算器来使用？

\mod 5

考虑 5 的简化剩余系 \{1,2,3,4\} ，我们有 2*2=4,\ 4*2\equiv 3,\ 3*2\equiv 1

因为 x*1=x ，那么我们令 *1 等价于不做操作

现在我们需要找到一个操作序列，使得其每做一次结果均不同，且执行 4 次后等价于未执行，显然 \{U\} 符合条件

那么 *1\rightarrow \{\},\ *2\rightarrow \{U\},\ *3\rightarrow \{U'\},\ *4\rightarrow \{U2\} ，我们有循环 2\rightarrow 4\rightarrow 3\rightarrow 1

\mod 10

还是考虑 10 的简化剩余系 \{1,3,7,9\} ，此时存在 3 的阶为 4，那么我们令 *3\rightarrow\{U\} ，其余数字同上

此时循环为 3\rightarrow 9\rightarrow 7\rightarrow 1

\mod 20

简化剩余系 \{1,3,7,9,11,13,17,19\} 中 \{11,13,17,19\} 等价于 \{-9,-7,-3,-1\} ，那么我们令 *(-1)\rightarrow\{D2\} ，也即 *19\rightarrow\{D2\}

例如 7*11*3*17\equiv 7*(-9)*3*(-3)\rightarrow\{U',U2,D2,U,U,D2\}=\{U'\}\rightarrow 7

\mod 100

此时简化剩余系的大小为 40 ，如果我们使用上述思路，还需找一个大小至少为 5 的循环 (4*2*5=40)

打表可知，100 以内阶为 5 的数均能由 21 生成，而阶为 4 的循环由 7 生成，也就是说我们现在有三个循环 A: 7\rightarrow 49\rightarrow 43\rightarrow 1, B: 21\rightarrow 41\rightarrow 61\rightarrow 81\rightarrow 1, C: 99\rightarrow 1

计算发现，\{abc\mod 100\ |\ a\in A,b\in B,c\in C\} 恰是 100 的简化剩余系

熟悉群论数论的读者可能发现，我们实际上给出了一组生成元，而不取用 \{3,99\} 则是因为 3 的阶过大，难以用魔方展现

鉴于笔者既不是群论大师也不是数论大师，因此数学证明望读者补充（

那么现在我们需要设计一组操作方案，使得这组方案操作 5 次等价于没操作，并且由于 C 循环只需要 2 个状态，我们也需要重新设计使得占用空间变少

鉴于笔者更不是魔方大师，在此直接给出构造（

等价于交换中心块左右的棱块

等价于更改中心块下方的棱块

读者可自证构造的正确性

而对于构造的直观显示， \mod 1000,\ \mod 10000,\ \mod 120120 的扩展问题，读者可查阅原视频

BV17W4y1S7WR 这道智力题的答案，在你意料之中吗？【官方双语】

对于最普通的策略，如果每名囚犯随机开箱，那么成功的概率为 P=(\frac 12)^{100} ，显然这可看作不可能事件

但我们考虑排列是若干个环组成的图，每个人能开 50 次箱，而环长超过 50 的环最多只有一个

因此，如果第 i 个人按 i\rightarrow p_i\rightarrow p_{p_i}\rightarrow p_{p_{p_i}}\rightarrow \dots 的顺序开箱，直到他找到自己的编号，那么成功与否就从个人独立转移到了环独立，且最多只有一个环失败

也即，失败 \iff 图中出现了长度超过 50 的环，这个策略的成功率骤升到了 P\approx 31\% ，现在我们证明这一点

由于最多只有一个环环长超过 50 ，我们计算失败的概率，也即图中出现环长超过 50 的环的概率

枚举环长 L\ge 51 ，出现环长为 L 的环概率为 P(maxL=L)=\frac{\binom{100}{L}\frac{L!}L(100-L)!}{100!}

表示，先从 100 个数中任取 L 个数组成环，这 L 个数排成一行按顺序链接成环有 L! 种方案，但每个方案循环移位计算了 L 遍，即本质不同的方案数只有 \frac{L!}L 个，剩下的 100-L 个数任意互相链接有 100-L 种方案，乘起来再除掉总方案数 100!

简单化简可以得到 P(maxL=L)=\frac 1L

那么 P(success)=1-\sum_{i=51}^{100} \frac 1i ，暴力计算可得 P(seccess)\approx 31\%

那么人数增多时会发生什么？考虑 2n 个人去打开 n 个箱子时，P(success)=1-\sum_{i=n+1}^{2n} \frac 1i

我们计算后部分和式的极限，\lim_{n \to \infty} \sum_{i=n+1}^{2n} \frac 1i = lim_{n\to\infty} \int_{n}^{2n} \frac1x dx=lim_{n\to\infty} \ln(x)+C|_{n}^{2n}=\ln 2

也就是说，lim_{n\to\infty} P(success)=1-\ln2

假设现在有一个警卫知道了整个排列，他希望囚犯们成功，那么他可以通过一次交换，来使策略的成功率提升到 100\%，即将最长环断为两个半环

假设现在有另一个警卫，他不希望囚犯们成功，只要囚犯们知道他会任意交换盒子，他就不能使囚犯们 100\% 失败，这是因为囚犯可以将盒子编号统一 +5 来将重新生成图