A

难度：橙

算法一

直接爆搜，复杂度 $O(4^nn^4)$，期望得分 $2$。

算法二

我们来找找规律呢：欸怎么 $n>2$ 输出都是 $0$ 啊？

于是直接判断，$n\le 2$ 输出 1，否则输出 $0$。期望得分 $100$。

事实上可以简单地证明 $n>2$ 时答案都是 $0$。

一个长度大于 $2$ 的串，一定存在一个数字（$7$ 或 $9$）出现次数大于 $1$。那么，令 $l_1=r_1=pos_1,l_2=r_2=pos_2$，得到的 gcd 一定等于这个数字。因此，我们把某个串中所有满足 gcd 为 7 和 9 的长度为 1 的区间对拿出来组成两个集合，这两个集合就可以唯一确定这个串。

B

难度：绿

Q：为什么暴力分这么高？

A：这题相对第一题来说比较难，暴力分放多一点比较良心。

Q：为什么我写正解得了 0 分，每个 Subtask WA 1~2 个点？

A：你可能没特判操作次数没用完时已经排好序了的情况。试试这组数据：

input:
2 1
1 2
output:
2 1

算法一

枚举所有可能的最终排列，再判断能否恰好交换 $K$ 次得到，可以先求最小交换次数，然后看奇偶性。复杂度 $O(n!)$，期望得分 $30$。

$K=10^{12}$ 那答案要么是 $1,2,...,n$ 要么是 $1,2,...,n,n-1$，只需要判逆序对数的奇偶性。复杂度 $O(n^2)$ 或 $O(n\log n)$，期望得分 $45$。

算法二

从前往后贪心。

设当前位置为 $i$，已经确定了 $1\sim i-1$ 位置字典序最小的答案，现在还剩 $m$ 次操作。那找到 $[i,\min(i+m+1,n)]$ 区间内的最小元素，把这个元素交换至 $i$。

假如已经交换成 $1\sim n$ 了操作还有剩余：剩偶数次则无影响，剩了奇数次就要交换 $n-1,n$。

暴力找区间最小元素，时间复杂度 $O(n^2)$，期望得分 $75$。

算法三

注意到“把这个元素交换至 $i$”其实相当于区间剪切，把 $[i,p-1],[p,p]$ 变成 $[p,p],[i,p-1]$，可以用平衡树维护。再维护个区间最小值及其位置即可。也可以用权值线段树 / 树状数组维护，不过因为出题人写的平衡树，时限开得很大。

时间复杂度 $O(n\log n)$，期望得分 $100$。

C

难度：紫

算法一

当 $n\le 10^5$ 时，可以枚举行，问题转化为求 $1\sim R$ 的 $k$ 进制下异或和（前缀和相减即可）。这可以按位统计，$O(\log R)$ 求出。复杂度 $O(n\log nm)$，期望得分 $18$。

计算过程中可能会爆 long long，最好开上 __int128。

算法二

$nm$ 总体很小，考虑设置阀值分类讨论。

若 $n\le B$，使用算法二。

否则，枚举列，按位考虑，考虑第 $a$ 位，相当于求

$$\sum_{i=l}^r \dfrac{im+j}{K^a}\ \mathrm{mod}\ K$$

类欧即可。

时间复杂度 $O(\max(B\log nm,\dfrac{nm}{B} \log^2 nm))$，当 $B=O(\sqrt{nm\log nm})$ 时最优，为 $O(\sqrt{nm}\log^{1.5}nm)$。

第二个 Subtask 可直接实现，第一个、最后一个 Subtask 需要取模优化，而且需要选手处理 long long 的溢出，细节非常多，因此只放了 39 分 （时限还是开到了 std 两倍以上，常数较好的话可能不优化也可以过） 洛谷总时限太小，导致必须卡常数，建议去 InfOJ 提交。

D

难度：紫

算法一

暴力枚举所有情况。复杂度 $O(2^nn)$，期望得分 $1$。

可以 dp，设 $f_{i,S}$ 为前 $i$ 个字符，最后 $k$ 个字符形如 $S$ 的方案数，转移显然。时间复杂度 $O(n2^k)$，期望得分 $9$。

算法二

使用矩阵快速幂优化上面的 dp。

结合实现精细程度和 $a=0$ 情况，可以得到 $12\sim 52$ 分不等。

时间复杂度 $O(8^k\log n)$。

算法三

使用 BM 算法求出 $k,a$ 固定时 $ans_n$ 的最短递推式。

经过打表验证，$k\le 14$ 时最短递推式长度不超过 $4719$。结合常系数齐次线性递推的 $O(m\log m\log n)$ 算法（其中 $m=4719$），可以做到 $O(m^2+m\log m\log n)$ 的复杂度（单组数据）。

视线性递推算法实现可以获得 $64\sim 100$ 分。

本题对常数没有太多要求，std 完全不卡常。