AtCoder Regular Contest 148 D – mod M Game
鲁莽的尝试？
一个非常显然的 Bob 的必胜局面是：对于任意 $x\in \{0,1,\cdots,M-1\}$，在这 $2N$ 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。
那……其他局面就一定是 Alice 必胜么？
我们只依靠该结论交一份代码。不出意料，没有通过。不过它只错了两成的测点！看来大体方向是正确的。
分类： 数学
-
第二届天元编程邀请赛（提高组） 解题报告
一场相当有收获的比赛。比赛链接
A – 石老板举世无双
解法一
尝试观察规律。我们发现，在完成$s$次操作以后，左端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]$，右端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)$。假如现在我们达到最终状态，其$l=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}$。那么，在$x$的二进制表示中，如果从高到底第$\mathrm{pos}$位为$1$，则在第$\mathrm{pos}$轮中，有
check (mid) == 0，向右区间递归；否则向左区间递归。这是很容易解释的：若向右递归，则右端点不变。而在下一层，右端点表示中$a, b$的所有系数乘$2$，所以体现为二进制位末尾添一个$0$。反之，就变成$(x+(x+1))/2$，在下一层中体现为$2x+1$。如果其有$\operatorname{popc}(x)$位为$1$，则到达该状态的概率为$p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$。以$s=3$时的状态$l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}$为例。$2$的三位二进制表示为$\text{0b010}$，则推断出在前三轮分别向右、左、右区间递归，到达其的概率为$p_0p_1^2$。 （更多…）
-
AtCoder ARC138D – Differ by K bits 简略题解
考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。
由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。
考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。
可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。
下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。 （更多…）
-
AtCoder ARC134C – The Majority – 简略题解与思路重现
AtCoder ARC 134 C – The Majority
如此ruzhi的一道题目竟花去两小时有余，比赛结束也没写出来，实在惭愧。
拿到题目，很快想到一种DP：令$f(i, j, k)$表示“考虑到第$i$个盒子，第$1$种小球用去$j$个，第$2, 3, \dots, n$种小球用去$k$个”的方案数。
容易转移。然后发现$a_i$是$10^9$级别。同时题目告诉我们，相同类别小球无法区分，所以要是上述做法正确，为什么要分别给出$a_2, a_3, \dots$呢？如何在转移时确保每一种小球的使用次数正确？立刻想到正解与$\mathrm{O}(a_i)$基本无关。
-
AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP
昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。
今天查看题解，发现有几个重要的，从未考虑过的trick：
- 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
- 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。