题解：中二病DNA疫苗问题

问题核心

给定环形DNA的$n$段和距离阈值$k$，需解决两个问题：

1. 不考虑旋转，求满足“任意两段距离≥$k$”的非空子集数（记为$ans1$）。
2. 考虑旋转等价（旋转后相同的子集算一种），求本质不同的非空子集数（记为$ans2$）。

距离定义：两段中间隔的最少段数$+1$，如第$n$段与第$1$段距离为$1$；答案需对$10^9+7$（记为$MOD$）取模。

一、求解$ans1$：不考虑旋转的非空子集数

关键思路：线性→环形转化

环形的约束比线性更紧（需额外保证第$1$段与第$n$段的距离≥$k$），因此先计算线性情况的独立集数目，再修正为环形。

1. 线性情况的独立集数目（含空集）

定义$f(x)$为“线性排列的$x$段DNA，满足任意两段距离≥$k$的子集数（含空集）”，递推关系如下：

• 递推公式：$f(x) = (f(x-1) + f(x-k)) \mod MOD$
  解释：对第$x$段，有两种选择——不选（则前$x-1$段的子集数为$f(x-1)$）；选（则前$x-k$段不能选，子集数为$f(x-k)$）。
• 边界条件：$f(x) = 1$（若$x < 0$，视为空集的特殊情况）；$f(0) = 1$（空集本身）。

2. 环形情况的独立集数目（含空集）

定义$g(n)$为“环形排列的$n$段DNA，满足条件的子集数（含空集）”。环形需排除“线性中合法但第$1$段与第$n$段距离<$k$”的子集：

• 第$1$段与第$n$段的距离恒为$1$，因此仅当$k>1$时，需排除“同时包含第$1$段和第$n$段”的线性子集。
• 这类子集的数目为$f(n-2k)$（中间$n-2k$段的独立集数，含空集；若$n-2k < 0$，取$f(n-2k)=1$）。

因此：

• 若$k=1$：所有子集均满足条件，$g(n) = f(n) = 2^n$（因$k=1$时$f(x)$递推为$2^x$）。
• 若$k>1$：$g(n) = (f(n) - f(n-2k)) \mod MOD$（需保证结果非负，可加$MOD$后再取模）。

3. 计算$ans1$

$g(n)$含空集，因此非空子集数为：

$$ans1 = (g(n) - 1) \mod MOD$$

二、求解$ans2$：本质不同的非空子集数

关键工具：Burnside引理

旋转等价类数目 = 所有旋转操作的不动点子集数的平均值。旋转群含$n$个操作（旋转$0,1,...,n-1$个位置），步骤如下：

1. 不动点子集数$C(t)$（旋转$t$个位置）

对旋转$t$，记$d = \gcd(t, n)$（循环个数），$L = n/d$（每个循环的长度）。不动子集需满足“选整个循环或不选”，且循环内/间满足距离约束：

• 若$d < k$：循环内段的距离为$d < k$，选循环会违反条件，因此仅空集合法，$C(t) = 1$。
• 若$d ≥ k$：循环内段的距离≥$d ≥ k$，合法。此时选择循环的问题等价于“长度为$d$的环形DNA的独立集数（含空集）”，即$g(d)$（同$g(n)$的定义，仅将$n$替换为$d$），因此$C(t) = g(d)$。

2. 按约数分组计算总和

$d$必为$n$的约数，对每个约数$d$，统计满足$\gcd(t, n)=d$的$t$的个数（即$\phi(n/d)$，欧拉函数），则所有旋转的不动点子集数总和为：

$$sum_C = \sum_{d | n} \left[ \begin{cases} \phi(n/d) \times 1 & (d < k) \\ \phi(n/d) \times g(d) & (d ≥ k) \end{cases} \right] \mod MOD$$

3. 计算$ans2$

• 所有子集（含空集）的本质不同数目：$S = (sum_C \times inv(n)) \mod MOD$，其中$inv(n)$是$n$在$MOD$下的逆元（因$MOD$是质数，$inv(n) = \text{pow}(n, MOD-2, MOD)$）。
• 减去空集的等价类（1个），得：

$$ans2 = (S - 1) \mod MOD$$

三、预处理与复杂度分析

1. 预处理内容

• $f(x)$：用数组存储$x$从$0$到$n$的取值，递推时间$O(n)$。
• $pow2(x)$：预处理$2^x \mod MOD$（$x$到$n$），用于$k=1$时的$g(d)$计算，时间$O(n)$。
• 欧拉函数$\phi(m)$：对$m$从$1$到$n$，用筛法预处理，时间$O(n \log \log n)$。
• $n$的约数：枚举$1$到$\sqrt{n}$，找出所有约数，时间$O(\sqrt{n})$。

2. 总复杂度

$O(n \log \log n + \sqrt{n})$，可处理$n ≤ 10^5$的范围。

四、样例验证

样例1：输入$5 2$

1. 预处理$f(x)$：$f(0)=1, f(1)=2, f(2)=3, f(3)=5, f(4)=8, f(5)=13$。
2. $ans1$：$k=2>1$，$g(5)=13 - f(1)=11$，$ans1=11-1=10$。
3. $ans2$：
   • $n=5$的约数：$1,5$。
   • $d=1$：$\phi(5)=4$，$d<2$，贡献$4×1=4$。
   • $d=5$：$\phi(1)=1$，$g(5)=11$，贡献$1×11=11$。
   • $sum_C=15$，$inv(5)=200000001$，$S=15×200000001=3$，$ans2=3-1=2$。

样例2：输入$6 1$

1. $ans1$：$k=1$，$g(6)=2^6=64$，$ans1=64-1=63$。
2. $ans2$：
   • $n=6$的约数：$1,2,3,6$。
   • $d=1$：$\phi(6)=2$，$g(1)=2^1=2$，贡献$2×2=4$。
   • $d=2$：$\phi(3)=2$，$g(2)=4$，贡献$2×4=8$。
   • $d=3$：$\phi(2)=1$，$g(3)=8$，贡献$1×8=8$。
   • $d=6$：$\phi(1)=1$，$g(6)=64$，贡献$1×64=64$。
   • $sum_C=84$，$inv(6)=166666668$，$S=14$，$ans2=14-1=13$。

五、总结

1. $ans1$通过“线性递推→环形修正”计算，核心是$g(n)$的推导。
2. $ans2$基于Burnside引理，将旋转操作按约数分组，利用$g(d)$简化不动点计算。
3. 预处理欧拉函数、递推数组和幂次是高效求解的关键。