Contest Info

date: 2018.10.23 14:15-16:25

practice link

Solutions

A. Fair

签到题。

B. Petr and Permutations

签到题。

C. AND Graph

题目大意：给你若干个互不相等的 \(n\) 位（二进制下）整数，若 \(x\text{&}y=0\)，那么在 \(x\) 和 \(y\) 间连一条边。求这个图的联通块数量。

题解：补充 \(2^{n}\) 个点，记为 \((0,0)\sim(2^{n}-1,0)\)。建立有向图：

• \(x\to (x,0)\)
• \((x,0)\to (x\text{|}2^{\text{bit}},0)\)，其中 \(x\) 的 \(\text{bit}\) 位为 \(0\)
• \((x,0)\to \sim x\)

显然 \(x\) 有一条路径到 \(y\)，当且仅当 \(x\text{&}y=0\)。那么我们 dfs 一下即可。

D. Perfect Encoding

题目大意：求满足 \(\prod_{i=1}^{m}b_{i}\ge n\) 的 \(\sum_{i=1}^{m}b_{i}\) 的最小值。\(n\le10^{1.5\times10^{6}}\)。

题解：显然 \(b\) 中只有 \(2\) 和 \(3\)，且 \(2\) 至多有 \(2\) 个。我们枚举 \(2\) 的数量之后，问题变为大整数对 \(3\) 取 \(\log\)。事实上我们只要取前若干位并结合位数，很容易得到一个误差不超过 \(1\) 的估计值，快速幂计算后比较即可。

本题十分卡常，最后懒得搞了。这年头 FFT 都能 \(1.5e6\) 了吗。。。

E. Prince’s Problem

题目大意：给你一棵树，每个点有一个权，给出若干个询问 \(u, v, x\)，求 \(u\) 到 \(v\) 的路径上所有点的权和 \(x\) 的 \(\gcd\) 的积。

题解：离线，对每个质数分别处理。那么相当于要求路径上所有点的权跟某个 \(x\) 取 \(\min\) 的和。我们对 \(x\) 从小到大分别计算，计算完 \(x\) 后，把所有点权大于 \(x\) 的点都加 \(1\)，再接着计算 \(x+1\)。在欧拉序上用树状数组维护即可。

F. Oppa Funcan Style Remastered

题目大意：问你能否构造一个 \(n\) 的排列，使得它以 \(k\) 为周期，且 \(p_{i}\neq i\)。

题解：显然问题等价于 \(k\) 的质因子能否线性组合出 \(n\)。首先若 \(n\ge p_{1}p_{2}\)，一定有解。否则：

• 若 \(k=1\)，不能

• 若 \(k\) 有 \(1\) 个质因子，那么能组合当且仅当 \(p_{1}\mid n\)

• 若 \(k\) 有 \(2\) 个质因子，判断二元一次不定方程是否有自然数解即可

• 若 \(k\) 有 \(3\) 个质因子，枚举 \(p_{3}\) 用了几个，转化为上一种情况

• 若 \(k\) 的质因子超过 \(3\) 个，直接背包