题目分析

问题本质

在 $B$ 进制下构造一个 $n$ 位数 $x$，使得 $2x$ 的数位是 $x$ 数位的一个排列，且对应位不同时为 $0$。

数学建模

数位表示

设 $x$ 的 $B$ 进制表示为：

$$x = d_1B^{n-1} + d_2B^{n-2} + \cdots + d_n$$

其中 $0 \leq d_i < B$，且 $d_1 \neq 0$。

$2x$ 的表示为：

$$2x = e_1B^{n-1} + e_2B^{n-2} + \cdots + e_n$$

约束条件

1. 排列条件：$\{d_1, \dots, d_n\}$ 和 $\{e_1, \dots, e_n\}$ 作为多重集相等
2. 非零条件：对任意 $i$，$d_i$ 和 $e_i$ 不同时为 $0$
3. 首位非零：$d_1 \neq 0$

关键观察

循环数性质

著名的 $142857$ 是十进制下的循环数，满足：

$$142857 \times 2 = 285714$$ $$142857 \times 3 = 428571$$ $$142857 \times 4 = 571428$$ $$142857 \times 5 = 714285$$ $$142857 \times 6 = 857142$$

这种数在数学上称为循环数，与分数 $1/7$ 的循环节有关。

一般化构造

对于 $B$ 进制，如果存在 $n$ 使得 $B^n \equiv 1 \pmod{2n+1}$（或类似条件），则可能存在循环数。

解法思路

思路1：数学构造法

基于循环节的构造：

• 考虑分数 $\frac{1}{p}$ 在 $B$ 进制下的循环节
• 如果循环节长度为 $n$，且 $p$ 与 $B$ 互质，则循环节可能满足条件
• 需要验证 $2$ 倍后仍是排列

具体步骤：

1. 寻找满足条件的素数 $p$
2. 计算 $\frac{1}{p}$ 在 $B$ 进制下的循环节
3. 验证 $2$ 倍后是否为排列

思路2：搜索 + 剪枝

DFS搜索框架：

• 从高位到低位依次确定 $x$ 的每一位
• 同时计算 $2x$ 的对应位（考虑进位）

剪枝策略：

1. 数位和检查：$x$ 和 $2x$ 的数位和必须相等
2. 模运算检查：$x \equiv 2x \pmod{B-1}$ 蕴含特定条件
3. 首位约束：$d_1 \neq 0$，且 $2d_1$ 的进位影响
4. 排列可行性：维护已用数字的计数

思路3：方程求解

建立方程系统： 设置换 $\pi$ 满足 $e_i = d_{\pi(i)}$，则：

$$2\sum_{i=1}^n d_i B^{n-i} = \sum_{i=1}^n d_{\pi(i)} B^{n-i} $$

这可以转化为关于 $d_i$ 的线性方程组，但包含置换的不确定性。

特殊情况分析

$B = 3k - 1$ 的情形

• 测试点18,19：可能有系统构造方法
• 可能与模 $3$ 的性质有关

$B = 3k$ 的情形

• 测试点20,21：$B$ 是 $3$ 的倍数
• 可能需要不同的构造策略

小数据情形

• $n \leq 8$：直接暴力搜索
• $n \leq 15$：DFS + 强剪枝

算法选择策略

基于数据范围

• 小数据（$n \leq 15$）：DFS搜索
• 中等数据（$n \leq 100$）：数学构造 + 验证
• 大数据（$n \leq 2\times 10^5$）：必须找到 $O(n)$ 或 $O(1)$ 的构造方法

基于进制 $B$

• 小 $B$：搜索更可行
• 大 $B$：需要数学构造
• 特殊 $B$：利用数论性质

构造技巧

循环移位构造

如果找到长度为 $n$ 的数字 $x$ 满足 $2x$ 是 $x$ 的循环移位，则自动满足排列条件。

模式填充

对于某些 $B$ 和 $n$，可以找到固定的数字模式，通过填充生成解。

无解判断

必要条件

1. 数位和：$x$ 和 $2x$ 的数位和相等
2. 模性质：在模 $B-1$ 下的约束
3. 奇偶性：某些情况下奇偶性矛盾

充分条件

对于某些 $(n, B)$ 组合，可以通过数学证明无解：

• 如样例中的 $n=3, B=3$

实现考虑

多组数据处理

• 预处理常见 $(n, B)$ 组合的解
• 对每个查询快速判断和构造

大数运算

• $n$ 可达 $2\times 10^5$，需要高效的大数表示
• 避免实际计算 $2x$，而是通过模式构造

总结

本题的核心在于发现和利用数论性质进行构造。对于小数据可以用搜索，对于大数据需要找到数学上的构造模式。关键在于理解循环数与分数循环节的关系，以及如何推广到任意进制。