C. Number 题解
构造三个长为 \(B\) 的 \(B\) 进制数 \(P,Q,R\)，要求满足 \(P,Q,R\) 的每一位数字构成 \(0\sim B-1\) 的排列，且 \([P]_B+[Q]_B=R_{B}\)。
\(B\leq 10^6\)
很久没做这么古典的构造题了，也没做出来而且焦头烂额了。官方题解的思考高度很高但是看了几遍才看懂，这里简单给未来的自己陈述一下。详细思路还是建议看官方题解和讲解视频。
奇数无解
关于这个结论，我的证明如下（非官方）：
考虑 \(P,Q,R\) 对 \(B-1\) 取模的结果，以 \(P=(p_0,p_1,\dots,p_{B-1})\) 为例。
\[\begin{align} P&\equiv \sum_{i=0}^{B-1} p_iB^i\pmod{B-1}\\ &\equiv \sum_{i=0}^{B-1} p_i[B\bmod{(B-1)}]^i \pmod{B-1}\\ &\equiv \sum_{i=0}^{B-1} p_i \pmod{B-1}\\ &\equiv \frac{B(B-1)}{2}\pmod{B-1} \end{align} \]当 \(B\) 为奇数时，取值为 \(\frac{B-1}{2}\)，\(P+Q\neq R\)。无解
当 \(B\) 为偶数时，取值为 \(0\)，\(P+Q=R\)，满足有解的必要条件。
进位位置数为 \(\frac{B}{2}\)
然而这个证明并未带来更多结论，题解是这样证明的
设五元组 \((p_i,q_i,r_i,c_i,d_i)\)，表示第 \(i\) 位上 \(P,Q,R\) 上的数字位 \(p_i,q_i,r_i\)，由 \(i-1\) 位对这位有 \(c_i=0/1\) 的进位值，对 \(i+1\) 位产生了 \(d_i=0/1\) 的进位值。
同时对每个五元组内部，有
\[p_i+q_i+c_i=r_i+Bd_i \]有 \(c_0=0,d_{B-1}=0,c_i=d_{i-1}\)。同时设 \(C=\sum c_i=\sum d_i\)，\(S=\sum p_i=\sum q_i=\sum r_i\)。
对 \(B\) 个二元组累加，有
\[S+S+C=S+BC\implies C=\frac{B}{2} \]故 \(B\) 为奇数时是无解的，同时也说明了设内部进位总数 \(C=\frac{B}{2}\)
思路
假设我们得到了合法答案的所有五元组 \((p_i,q_i,r_i,c_i,d_i)\)，但是它们现在的顺序是乱的，如何找到答案？
设当前需要考虑的进位状态为 \(x=0/1\)，第 \(0\) 位需要考虑的进位 \(c_0=0\)，则初始的进位状态为 \(0\)。
这是一个两个点的图，没有一个五元组，考虑连一条 \(c_i\to d_i\) 的有向边，在这个图上 \(0\) 的点开始求一条欧拉回路，一定能回到 \(0\) 这个状态且经过 \(B\) 条边，欧拉回路上边的顺序就是五元组的顺序，即答案从低位到高位的顺序。
具体构造
我也不知道怎么来的，但是你玩一下就会发现有了上面的思路就非常合理。
直接 \(p_i=i,q_i=(i-2)\bmod B\)，那么
可以发现 \(2i-2\bmod B\) 这个东西只能覆盖所有模 \(B\) 下为偶数的数，且每个数两次，一旦一半的 \(c_i\) 为 \(1\)，则恰好可以奇数偶数各覆盖一次。
只需要 \(c_{0\sim \frac{B}{2}-1}=1\)，\(c_{\frac{B}{2}\sim B-1}=0\) 即可以满足 \(r_i\) 是完整排列，但是这样会在 \(i=1\) 时 \(p_i=r_i\)，将 \(c_1\) 与 \(c_1,c_{\frac{B}{2}+1}\) 互换值即可。
同时你会发现恰好进位 \(d_i\) 也在一半的位置为 \(1\)，这个已经由 \(p_i+q_i\) 满足。
具体实现见代码
const int N=1000006;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,idx[N],p[N],q[N],r[N],a[N],d[N];
int main(){scanf("%d",&n);if(n==4){puts("0 1 2 3");puts("1 3 0 2");puts("2 0 3 1");return 0;}if(n%2==1||n==2)return puts("-1"),0;for(int i=0;i=0;--i){// printf("%d ",idx[i]);// }puts("");for(int i=n-1;i>=0;--i){printf("%d ",p[idx[i]]);}puts("");for(int i=n-1;i>=0;--i){printf("%d ",q[idx[i]]);}puts("");for(int i=n-1;i>=0;--i){printf("%d ",r[idx[i]]);}puts("");return 0;
}
/*9 8 7 6 5 4 3 2 1 07 6 5 4 3 2 1 0 9 80 0 0 1 0 1 1 1 0 1
16141211 8 7 5 310 96 4 2 1 8 7 5 3 0 91 1 1 1 0 0 0 0 1 09 8 7 6 5 4 3 2 1 07 6 5 4 3 2 1 0 9 80 0 0 0 0 1 1 1 1 1
16141210 8 7 5 311 96 4 2 0 8 7 5 3 1 91 1 1 1 0 0 0 0 1 0
*/