m c o i r 9 e d i t o r i a l

w33z8kqrqk8zzzx33 · 2021-06-26 18:02:13 · 个人记录

非常抱歉 B 撞原题了 /kk

Calculating Entropy

如果提前知道 \log n 就很简单，直接在 1 到 2^{\log n} 之间二分，使用 \log n 操作。但是在这里不知道 \log n。

第一个方法是倍增，依次枚举 \log n 的可能值，直到有 2^{???}>n。接下来再枚举二进制位。这样用 2\log n 操作。

也可以直接对 \log n 二分，用 \log n+\log\log n 操作，可过。

Vertex Induced Isomorphisms

做法 1：V_{n+1} 由两个相同左半和右半组成，其中左半和右半对应点之间互相连边。于是一个 V_k 同构子图要么从左半贡献，要么从右半贡献，要么由左半的一个 V_{k+1} 同构子图和右半的对应子图位置连起来构成。有地推方程组：

f_{0\ 0}=1\\ f_{n\ 0}=2f_{n-1\ 0}\\ f_{n\ k}=2f_{n-1\ k}+f_{n-1\ k-1} \end{cases}

考虑组合意义，这等价于有一张图，n-1\ k 和 n\ k 之间有两条边，n-1\ k-1 和 n\ k 之间有一条边。则怎么走都需要夸恰好 n-k 个 n-1\ k\Rightarrow n\ k 边，选择这些边在什么位置有 \binom nk 方案，选择走哪条有 2^{n-k} 方案，答案为 \binom nk2^{n-k}。

做法 2：同样利用 f_{n\ k}=2f_{n-1\ k}+f_{n-1\ k-1}。令 f_n OGF 为 F_n，得：F_n=2F_{n-1}+xF_{n-1}，或 F_n=(2+x)F_{n-1}。由于 F_0=1，得 F_n=(2+x)^n，二项式定理展开得 [x^k]F_n=\binom nk2^{n-k}。

做法 3：考虑直接用组合意义。V_n 可以看做一个 n 维超立体。对于任何 k 维超子立体，需要选择哪些维属于超子立体，以及超子立体外的维度。得 \binom nk2^{n-k}。

Dream and Strings REMATCH

将 a_i 递增排序，排序后位置 2k 和 2k+1 配对。配对之后可以把值 a,b 合并为 b-a。

进行这样的操作，n 变为 n/2，最大值期望变为 \max/n。

进行 R 轮这样的操作，最大值期望变为 \frac{\max}{n^R}2^{\frac{R(R-1)}{2}}。将最大值降为 1 则需要 R=2\log n+1。时间复杂度 O(n\log^2n)。

Three Absolute Values

可以看出来本题就是 3SAT。~~可是我没有解决 3SAT 问题，~~ 考虑分析本题性质。

考虑 random walk SAT。先对每一个变量随机赋予一个值，再随机调整，其中调整为随机选一个不符合的方程并改变其中的一个随机变量。

当进行 3n 次这样的调整，可以分析出需要期望尝试 O((4/3)^n) 次，时间复杂度 \tilde O((4/3)^n)。

可以这样分析：

钦定一个最终状态，其中这个最终状态合法。
一个初始状态与该最终状态相差 k 个位置的概率为 \binom nk2^{-n}。
走 3k 步到达最终状态的概率大于等于走 3n 步到达最终状态的概率，于是分析调整 3k 次就到达最终状态的概率。
在这 3k 步中，最多有 k 次“走错”。这个的概率大于等于走错恰好 k 次，于是分析调整 3k 次并调整错 k 次就到达最终状态的概率。
调整错恰好 k 次的概率至少为 \binom{3k}k\frac{2^k}{3^{3k}}：这是默认每一次调整随机选择的方程只有一个变量调整能调整对。
这个表达式至少为 \frac{1}{\sqrt{6k}}2^{-k}。

得到成功的概率的下限：

P\ge\sum_{k=1}^n\left(\frac{2^{-k}}{\sqrt{6k}}\right)\binom nk2^{-n}\ge\frac{2^{-n}}{\sqrt{6n}}\sum_{k=1}^n\binom nk2^{-k}=\frac{1}{\sqrt 6n}(\frac 34)^n

实际上由于当问题足够稀疏，合法最终状态足够多，远远达不到这个下限。

由 "Linear upper bounds for random walk on small density random 3-CNFs"，当 m<1.637n，并 n\to\infty，正确的概率收敛至 1。

~~其实我出这道题来收集你谷神仙的各种 3SAT 启发式~~

Greedy Deletion

首先，由于当 k 为正整数，1<a,b，有 a^k+b^k<(ab)^k，可以只选择质数删除。

于是我们本质想做的是删除所有出现奇数次数的质数。

算法 1：根号分治 + 数论分块

注意到当 p>\sqrt n，p 出现次数为 \lfloor\frac{n}{p}\rfloor，可以对 p<\sqrt n 的质数暴力跳找到出现次数，对于 p>\sqrt n 处理出一个数前缀和，并用数论分块做。

时间复杂度 O(n+T\log n\sqrt n)，可以过 s123.

可以优化至 O(T\frac{n^{3/4}}{\log n})。

算法 2：前缀和预处理

考虑到差分后，每一个质数贡献只在它的倍数，于是对每一个质数暴力跳所有倍数，处理出这些倍数所包含多少次该质数。当包含次数的前缀和从偶数变成奇数，需要在这个位置标记上开始删掉；当从奇数变成偶数，则可以删掉这个标记。

时间复杂度 O(n\log\log n+T)。

算法 3：质因子预处理

从 1 到 n 依次扫描。用线性筛预处理每一个数的最小质因子，这样可以统计出每一个数的所有质因子。

维护当前前缀出现奇数次是哪些质数；则在从 i-1 转到 i 的时候需要 “开” 一些质数，也需要 “关” 一些质数。

考虑每一个质数仅在它的倍数形成贡献，时间复杂度 O(n\log\log n+T)。

其实是算法 2 的转置。