题解：P17206 「DLESS-6」Lost Requiem
P2441M
·
·
题解
设 $g(x,y)$ 为对应置换的不动点个数，由 Burnside 引理，所求即为
$$
\dfrac{1}{n(n-1)}\sum_{x=1}^{n-1}\sum_{y=0}^{n-1}g(x,y)
$$
设满足 $p_i=(xi+y)\bmod{n}$ 的排列 $p$ 有 $c(x,y)$ 个置换环，同一个置换环内必须填同一种数，于是 $g(x,y)=m^{c(x,y)}$。
考虑如何求出 $c(x,y)$。
若 $x=1,y=0$，则 $c(x,y)=n$。
若 $x=1,y\neq 0$，设从 $i$ 出发走 $k$ 步会回到 $i$，则 $ky\equiv 0\pmod{n}$，显然满足条件的最小正整数为 $k=n$，因此 $c(x,y)=1$。
若 $x\neq 1$，考虑 $t\equiv xt+y\pmod{n}$ 有唯一解。对于任意的 $i$，将其表示成 $i=t+j$，则 $x(t+j)+y\equiv t+xj\pmod{n}$，因此该置换实际上和 $y=0$ 对应的置换同构。对于 $i=0$，显然 $xi=0$，这会贡献一个置换环；对于 $i\neq 0$，还是设从 $i$ 出发走 $k$ 步会回到 $i$，则 $x^k\equiv 1\pmod{n}$，因此环长为 $\operatorname{ord}_n(x)$。加起来得到 $c(x,y)=1+\dfrac{n-1}{\operatorname{ord}_n(x)}$。根据经典结论，对于任意的 $d\mid(n-1)$，恰好有 $\varphi(d)$ 个元素的阶为 $d$。
综上，答案为
$$
\dfrac{1}{n(n-1)}\left(m^n+(n-1)m+n\sum_{\substack{d\mid(n-1)\\d>1}}\varphi(d)m^{1+\frac{n-1}{d}}\right)
$$
对 $n-1$ 做质因数分解，DFS 枚举约数的同时维护 $\varphi$ 的值即可。时间复杂度为 $\mathcal{O}(\sqrt{n}+\tau(n-1)\log{n})$。
:::success[主要代码]
```cpp
int tc, p, n, m;
vector<pii> vec;
mint sum;
mint qpow(mint a, ll b) {
mint res = 1;
for (; b; b >>= 1) {
if (b & 1) res *= a;
a *= a;
}
return res;
}
void fac(int n) {
vec.clear();
for (int d = 2; (ll)d * d <= n; ++d) {
if (n % d) continue;
int cnt = 0;
while (n % d == 0) {
n /= d;
++cnt;
}
vec.emplace_back(d, cnt);
}
if (n > 1) vec.emplace_back(n, 1);
}
void dfs(int x, int d, int phi) {
if (x == vec.size()) {
if (d != 1) sum += phi * qpow(m, (n - 1) / d + 1);
return;
}
auto [pr, cnt] = vec[x];
int pw = 1, ph = 1;
for (int i = 0; i <= cnt; ++i) {
dfs(x + 1, d * pw, phi * ph);
if (i == cnt) break;
pw *= pr;
ph = !i ? pr - 1 : ph * pr;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> tc >> p;
mint::setMod(p);
while (tc--) {
cin >> n >> m;
fac(n - 1);
sum = 0;
dfs(0, 1, 1);
cout << (qpow(m, n) + mint(n - 1) * m + n * sum) / (mint(n) * (n - 1)) << '\n';
}
return 0;
}
```
:::