SNOI2022 倍增

· · 题解

cnblogs。

本来想加强一下放 noip 模拟赛的，后来发现 loj 上已经有这种做法了，十分遗憾。

首先这题等价于对于 B 找到最小的满足条件的 n。因为可以在最优解里面插一堆 B-1。

这个 n 不会很大，因此一个比较暴力的想法是暴力枚举对应关系的排列和进位。

考虑把排列的环抠出来。不妨是 p_1 \to p_2 \to ... \to p_k \to (p_{k+1}=p_1)（这里的 p 表示排列对应位置上的值）。

不妨 c_i 是第 p_i 位得到的进位数量，那么 2p_i+c_i \equiv p_{i+1} \pmod B。

所以就有 2^k p_1 + \sum_{j=1}^{k} 2^{k-j} c_j \equiv p_1 \pmod B。

设 C = \sum_{j=1}^{k} 2^{k-j} c_j，显然 0 \le C < 2^k。

不妨设 (2^k-1)p_1 + C = tB，可以发现 0 \le t \le 2^k。

而有了 t 之后，由于 C \le 2^{k}-1，所以 (p_1,C) 只有 \Theta(1) 种方案。

然后我们就可以算出来每个位置被前面的那个位置进了多少位，向后面的那个位置进了多少位。

而最后的那个数就是 一条在 0,1 两个点的图上的欧拉回路。这就要求了 0 \to 1 和 1 \to 0 的边数相同。

我们抠出来的环的 0 \to 1 和 1 \to 0 的边数不一定相同，所以可能要选多个环。这个可以背包解决。

设 k 是答案，时间复杂度 \Theta(k2^k)。aclink。