题目分析

问题描述： 给定字符串长度 $n$ 和字符集大小 $K$，求有多少个长度为 $n$ 的字符串，其满足：该字符串或者是回文串，或者其某个循环移位是回文串（即“循环回文串”）。答案对 $mod$ 取模。

数据范围： $n \le 10^{18}$，$T \le 10$，模数 $p$ 可能是大质数。

算法核心思路

这道题的本质是运用 Burnside引理/Polya定理 的思想配合 容斥原理 来计数，同时因为 $n$ 很大，需要使用 Pollard's Rho 算法进行质因数分解。

1. 数学推导

一个字符串 $S$ 被称为循环回文串，当且仅当它属于某个“回文项链”。 我们需要计算长度为 $n$ 的循环回文串的数量。这可以通过枚举循环节长度（即 $n$ 的因子 $d$）来解决。

根据相关数学结论（基于 Burnside 引理的变体），答案的形式涉及到对 $n$ 的所有因子进行遍历求和。代码中 dfs 函数实际上是在计算如下公式（经过化简）：

$$\text{Ans} = \sum_{d | n} \left( K^{\lceil d/2 \rceil} \times \text{val}(d) \times \text{coeff}(n/d) \right) $$

其中：

• $d$：当前枚举的因子（代码中的 p）。
• $K^{\lceil d/2 \rceil}$：长度为 $d$ 的回文串数量。代码中的 g(p) 函数计算的就是这个值。
  • 如果 $d$ 是偶数，回文串前半部分确定后半部分，数量为 $K^{d/2}$。
  • 如果 $d$ 是奇数，中间一位也是自由的，数量为 $K^{(d+1)/2}$。
• $\text{val}(d)$：对于长度 $d$ 的回文串，其产生的不同循环移位数量的贡献因子。
  • 代码中体现为 (p & 1 ? p : p >> 1)。
  • 若 $d$ 为奇数，贡献为 $d$。
  • 若 $d$ 为偶数，贡献为 $d/2$。这是因为偶数长度的回文串在循环移位视角下存在对称性导致的重复（例如 abba 循环移位只有 2 种本质不同的回文形态，或者在项链计数中的特殊权重）。
• $\text{coeff}(n/d)$：这是一个容斥系数，用于处理非本原（primitive）串的重复计数问题。
  • 在代码的 dfs 中，变量 t 维护了这个系数。
  • 对于 $n/d$ 的每一个质因子 $q$，系数乘以 $(1-q)$。
  • 如果 $d$ 包含某质因子 $q$ 的次数与 $n$ 相同（即 $n/d$ 不含因子 $q$），则系数乘以 $1$。
  • 这实际上是在计算一种类似于欧拉函数 $\phi$ 的变体，用于筛选出以 $d$ 为最小循环节的贡献。

2. 代码实现关键点

由于 $n$ 高达 $10^{18}$，直接 $O(n)$ 或 $O(\sqrt{n})$ 枚举都是不可行的。

1. 大数分解 (Pollard's Rho)：

   • 为了获取 $n$ 的因子，代码使用了 Miller-Rabin 素性测试 (MR) 和 Pollard's Rho 启发式分解算法 (PR)。
   • init 函数将 $n$ 分解为 $p_1^{e_1} p_2^{e_2} \dots$，存储在数组 a (质数) 和 b (指数) 中。

2. DFS 枚举因子：

   • 利用分解后的质因数，通过 dfs 递归生成 $n$ 的所有因子 $d$。
   • 相比直接遍历 $1 \sim \sqrt{n}$，直接利用质因数生成因子的效率极高（对于 $10^{18}$ 内的数，因子个数通常不多）。

3. 光速幂 (分块预处理)：

   • 在计算 $K^{\lceil d/2 \rceil}$ 时，指数可能很大。普通的快速幂 ksm 是 $O(\log n)$ 的。
   • 代码使用了 分块预处理 策略（类似于 Baby-step Giant-step 的思想）来优化幂运算。
   • mi0, mi1, mi2, mi3 分别预处理了 $K$ 的 $2^0 \dots 2^{14}$, $2^{15} \dots 2^{29}$ 等范围的幂。
   • 这样可以将单次幂运算的时间复杂度从 $O(\log n)$ 降至 $O(1)$，极大地加速了 DFS 过程中的计算。

4. __int128：

   • 由于模数 $mod$ 接近 $10^9$ 或更大，中间乘法运算会爆 long long，因此使用了 __int128 (i7) 来保证取模前的精度。

题解总结

步骤：

1. 读入 $n, K, mod$。
2. 使用 Pollard's Rho 算法对 $n$ 进行质因数分解。
3. 预处理 $K$ 的幂次表，将 64 位整数拆分为 4 个 16 位的段，实现 $O(1)$ 查询 $K^x \pmod{mod}$。
4. 使用 DFS 根据质因数搜索 $n$ 的所有因子 $p$。
5. 在搜索过程中，根据公式 $\text{Ans} += g(p) \times \text{val}(p) \times \text{coeff}(n/p)$ 累加答案。
   • 其中系数 t 的更新逻辑为：若当前质因子未选满（即 $n/p$ 含有该质因子），则 t *= (1 - prime)；否则 t *= 1。
6. 输出最终累加的答案。

复杂度分析：

• 分解质因数：$O(n^{1/4})$ 期望复杂度。
• DFS：复杂度取决于 $n$ 的因子个数，对于 $10^{18}$ 范围内的数，因子个数上限很少（约 $10^5$ 量级），配合 $O(1)$ 的幂运算，完全可以在时限内通过。

这份代码是解决此类大数数论计数问题的标准且高效的模板。