ARC155
ARC155
A
考虑 \(k\le 2n\) 的情况，可以模拟，具体的，正着做一遍，填上对应的数字，反着做一遍，也填上对应的数字，如果合法，那么就是可以的。
考虑 \(k> 2n\) 的情况，容易发现等价于 \(k\bmod 4n\) 的情况，画个图：
红色部分，如果满足下面的两个串都是回文，那么上面的两个串自然都是回文。
实际上循环节是 \(2n\)，记 \(T'\) 表示 \(T\) 的翻转，即令 \(T'_i=T_{len-i+1}\cdots\)，考虑如果 \(TS\) 是回文，那么 \(S'T'\) 自然也是回文，所以如果把下图的 \(A'\) 换为 \(A\)，构造出满足条件的长度为 \(k-2n\) 的串 \(T\)，将 \(T'\) 带入进上面即可满足条件。
显然这种构造是充要的。
B
考虑式子 \(||x-a|-b|\)，取到最小值
\(0\) 的点为 \(a+b\) 和 \(a-b\)，考虑一个询问在一个点对上的答案，就是该区间的点到
\(a+b\) 和 \(a-b\)
距离的最小值，在多个点对上的答案就是到所有 \(a_i+b_i\) 或者 \(a_i-b_i\) 的最小值，维护一个
set 表示所有点，询问 lower_bound 即可。
C
变换问题，一般考虑找不变量。
操作可逆的变换问题，还可以考虑将两个序列同时向一个序列改变。
一般这种变换构造问题的思路是找不变量，但此题的不变量不容易找。
首先的必要条件是 \(A\) 是 \(B\) 的一个排列，以下讨论均认为 \(A\) 是 \(B\) 的排列。
注意到操作是可逆的，考虑将 \(A,B\) 同时变成一个串。如果 A 可以变成一个串，但 B 不能，则 A,B 不能变成同一个串。
考虑一个串 \(A\)，如果 \(A\) 中的任何奇数都无法移动，但 \(B\) 可以，那么显然是不行的，反之亦然。考虑如果 \(A,B\) 中的奇数都不能移动，那么以奇数为分割线，每个部分都要对应相同，对于长度大于 \(3\) 的偶数连续段，以可重集的形式相等，对于其它段，则以序列的形式相等。
如果 \(A\) 中的奇数可以移动，那么我们考虑将奇数全部移动到序列最前面。找到可以移动的两个奇数，将它们放在一起然后一直向后移动，如果碰到偶数可以直接移动，碰到奇数则移动这段奇数中最靠后的两个，直到这段奇数后没有奇数为止，然后考虑将这段奇数前的第一个偶数移动到这段奇数后面，如此操作，就可以将奇数全部放在最前面。
不少于三个偶数段可以任意交换，如果只有两个偶数，那么它们的顺序不能改变。
考虑对前面的奇数部分进行排序，将一个偶数移动到两个奇数之间，然后我们可以交换它们之后再将偶数移动回去，因此前面的奇数可以任意排序。
所以对于 \(A,B\)
中都存在可以移动的两个奇数的情况，如果偶数个数不为 \(2\)，答案一定为
Yes，否则如果出现顺序相同，为 Yes，顺序不同为
No。
D
高维前缀和
考虑这样一个问题，给定一个序列 \(a,a_i\in[1,n]\)，对于 \(i\in[1,n]\)，计算 \(a_i\) 中 \(i\) 的倍数的个数 \(b_i\)
一种 \(n\ln n\) 的做法是先算一个 \(cnt_i\) 表示 \(i\) 的个数，然后统计每个数 \(i\) 的倍数。
另一种方式是考虑高维前缀和，记 \(cnt_i\) 表示考虑到当且为止，\(i\) 倍数的个数，以任意顺序枚举 \(n\) 以内的质数 \(p_k\)，从大到小的令 \(cnt_i=cnt_i+cnt_{ik}\)。
复杂度是 \(n\log\log n\) 的。
为什么这样是对的，考虑将 \(i\) 视作一个 \(n\) 维的向量，每一维表示对应质数的指数，然后就是对每一维各自先做前缀和加起来。
解法一
考虑当前选好了一个数 \(A\)，所有的数已经可以被分为至多 \(2^6\) 类。
因为 \(2*3*5*7*11*13*17=510510>2\times10^5\)。
首先我们只关心具体有哪些质数而不关心质数的指数。
之后的选择一定会是在一个 DAG 上走，这个 DAG 的边数是 \(3^6\) 的。
考虑当前在 DAG 上的某个点，先手该如何决策，当前的数为 \(A\)，那么所有可以选的数被分为 \(A\) 的倍数，和非 \(A\) 的倍数，选非 \(A\) 的倍数一定会走到下一个点。
考虑到某个点后它的倍数的个数，等于所有它的倍数减去之前用掉的数的个数，注意我们在一个点处只关心其奇偶性，所以只需要记录一维 \(0/1\) 表示之前用掉了奇数个还是偶数个。
转移需要考虑同层转移和不同层转移，对于同层转移，先手当且仅当目前剩余奇数个的时候可以选择让后手走下一步。对于不同层转移，则只需要确定具体能转移到哪些点。
确定能转移到哪些点可以暴力，细节还是有点多。
改进解法
其实我们不需要这个 DAG，容易发现如果当前的 G 和用掉的数的个数就可以表达所有信息了，可以省掉建立 DAG 的步骤，同样的方式考虑 G 的同层转移和非同层转移。
对于非同层转移需要计算可以转移到哪些数字，记 \(f_{g,d}\) 表示满足 \(\gcd(g,A_i)=d\) 的 \(A_i\) 的个数，确定 \(g\) 之后从大到小枚举 \(d\)，计算出 \(d\) 倍数的个数，然后减掉所有 \(f_{g,kd}\)。
易知 \(g=ckd\)。
复杂度考虑每个 \(d\)，每个 \(d\) 的复杂度为 \(\frac{M}{d}\ln{\frac{M}{d}}\)。