以 \(0\) 为初始下标。
考虑到这个平台之间的转移不是很好处理，于是考虑换个角度，考虑每个高度。
这里定义高度为 \(i\) 的奶牛就是下一次操作要走 \(i\) 步的奶牛。
然后考虑去分析合法序列的性质。
性质 \(1\)：高度为 \(x\) 的奶牛在移动后的高度依然为 \(x\)，即这个过程可以看作每个高度中的平移。
证明：
考虑高度最大值 \(p\)，那么对于高度为 \(p\) 的平台位置 \(x\)，那么以这个平台开始的前 \(p\) 个平台肯定都需要过来一个奶牛，那么 \(x - p\) 的高度肯定为 \(p\)。
然后这部分是不会影响 \(\le p - 1\) 的这些高度的，便可以直接删掉这些奶牛，继续往下分析，就可以证出了。
考虑到对于高度为 \(p(p \ge 1)\)，相当于是每次平移 \(p\) 步，那么就会有 \(\gcd(p, n)\) 个循环节，这个是因为循环长度 \(l\) 满足 \(pl=kn\)，可以知道 \(l = \frac{\operatorname{lcm}(p, n)}{{p}}\)，对于循环节数量又有 \(cl = n\)，所以可以得到 \(c = \gcd(p, n)\)。
性质 \(2\)：对于最高高度 \(p(p\ge 1)\)，高度 \(< p\) 的奶牛都是满的。
证明：
考虑对于 \(p - 1\)，那么若 \(x\) 处有高度为 \(p\) 的，那么 \((x + p)\bmod n\) 处需要有高度为 \(p - 1\) 的，不然奶牛会掉下去，类似的，\((x + kp)\bmod n\) 都需要有高度为 \(p - 1\) 的。
相当于开头为 \((x + kp)\bmod (p - 1)\) 的循环节都需要选，发现因为 \(\operatorname{lcm}(p, p - 1) = p(p - 1)\)，所以 \(0 \le k < p - 1\) 对应的 \((x + kp)\bmod (p - 1)\) 的值都是不同的且肯定都走过了，所以每个循环节都需要有奶牛。
所以 \(p - 1\) 层是满的。
那么再往下的层，因为其上面一层是满的，其肯定也得是满的。
于是就可以考虑计数。
对于最高高度 \(= 0\) 的，方案数就是 \(1\)。
否则对于最高高度 \(= i\) 的，有 \(\gcd(i, n)\) 个循环节，可选可不选但必须选至少一个，对于不选的平台，其高度是确定的，所以方案数就为 \(2^{\gcd(i, n)} - 1\)。
答案就为 \(1 + \sum\limits_{i = 1}^{n - 1} (2^{\gcd(i, n)} - 1) = 1 - (n - 1) + \sum\limits_{i = 1}^{n - 1} 2^{\gcd(i, n)}\)。
时间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 1e9 + 7;
inline i64 qpow(i64 a, i64 b) {i64 v = 1; while (b) b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod; return v;}
int main() {
i64 n; scanf("%lld", &n);
i64 ans = (1 - (n - 1) % mod + mod) % mod;
for (i64 i = 1; i < n; i++) (ans += qpow(2, std::__gcd(i, n))) %= mod;
printf("%lld\n", ans);
return 0;
}
考虑优化。
因为 \(\gcd(i, n) | n\)，所以 \(\gcd(i, n)\) 的取值只会有 \(O(\sqrt{n})\) 种。
所以原式可以写成 \(1 - (n - 1) + \sum\limits_{1\le g < n, g | n} 2^g\sum\limits_{i = 1}^{n - 1} [\gcd(i, n) = g]\)。
考虑 \(\sum\limits_{i = 1}^{n - 1} [\gcd(i, n) = g] = \sum\limits_{i = 1}^{\frac{n}{g}} [\gcd(i, \frac{n}{g}) = 1]=\varphi(\frac{n}{g})\)。
于是原式为 \(1 - (n - 1) + \sum\limits_{1\le g < n, g | n} 2^g \varphi(\frac{n}{g}) = 1 - (n - 1) + \sum\limits_{1< g \le n, g | n} 2^{\frac{n}{g}} \varphi(g)\)。
可以在爆搜出 \(g\) 的同时维护 \(\varphi\)。
时间复杂度 \(O(\sqrt{n}\log n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
using i128 = __int128_t;
const i64 mod = 1e9 + 7;
inline i64 qpow(i64 a, i64 b) {i64 v = 1; while (b) b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod; return v;}
i64 n; int m;
std::vector<i64> P; std::vector<int> c;
i64 ans;
void dfs(i64 d, i64 phi, int w) {
if (w == m) {
d != 1 && ((ans += qpow(2, n / d) * phi) %= mod, 1);
return ;
}
dfs(d, phi, w + 1);
for (int i = 1; i <= c[w]; i++) d *= P[w], phi *= P[w] - (i == 1), dfs(d, phi, w + 1);
}
int main() {
scanf("%lld", &n);
i64 N = n;
for (i64 i = 2; i * i <= N; i++) {
int cnt = 0;
while (N % i == 0) cnt++, N /= i;
cnt && (P.push_back(i), c.push_back(cnt), 1);
}
if (N > 1) P.push_back(N), c.push_back(1);
m = P.size();
ans = (1 - (n - 1) % mod + mod) % mod;
dfs(1, 1, 0);
printf("%lld\n", ans);
return 0;
}