自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:38:24，当前版本为作者最后更新于2023-09-26 09:47:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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。