strarial 题解

思路一

题目分析

给定一个由 n 颗火种组成的项链，每颗火种可以对应 m 个黄金裔中的一个。项链可以旋转但不能翻转。求所有不同项链的夜魂值之和（夜魂值为各位置黄金裔编号之和），结果对 998244353 取模。

容易想到 Burnside 引理：一个置换群把被置换的数字分成等价类的个数等于这个置换群中各个元素（置换）不动点个数的平均数。

• 循环分解：对于旋转 k 步的置换，其循环节长度为 gcd(n, k)。
• 不动点计算：每个循环内的颜色必须相同。设循环节数目为 d，则每个循环的长度为 n/d。
• 贡献总和：每个循环的贡献为颜色值乘以循环长度，总共有 d 个独立循环，颜色选择的总和为 d * m ^ {d - 1} * m(m + 1) / 2。
• 置换数目：对应循环数目为 d 的置换数目为 $\varphi(\dfrac{n}{d})$。

综合所有因数的贡献，最终答案为：

$$\frac{(m+1)}{2} \times \sum_{d \mid n} \phi\left(\frac{n}{d}\right) \times m^d \mod 998244353$$

题解代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}
int euler_phi(int t) {
    if (t == 0) return 0;
    int res = t;
    for (int p = 2; p * p <= t; ++p) {
        if (t % p == 0) {
            res = res / p * (p - 1);
            while (t % p == 0) t /= p;
        }
    }
    if (t > 1) res = res / t * (t - 1);
    return res;
}
signed main() {
    int n, m;
    cin >> n >> m; m %= MOD;
    if (m == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> factors;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i != n / i) factors.push_back(n  / i);
        }
    }
    sort(factors.begin(),  factors.end()); 
    factors.erase(unique(factors.begin(),  factors.end()),  factors.end()); 
    int sum = 0;
    for (int d : factors) {
        int t = n / d;
        int phi = euler_phi(t); 
        int md = qpow(m, d);
        sum = (sum + 1LL * phi * md) % MOD;
    }
    int ans = (1LL * (m + 1) % MOD * sum % MOD) * qpow(2, MOD - 2) % MOD;
    cout << ans << endl;
    return 0;
}

思路二

引自 ZHL

说实话，这道题挺板的。

首先，我们学过 Pólya 定理，可以用来求它的黄金裔的构成方案数，但是题目问的是编号之和，所以我们就需要巧妙地转化。

怎么转化呢？

我们容易想到平均数，因为每个编号除了编号的大小都是等价的，所以我们直接在方案数上面乘上一个平均数，也就是 $\frac{m+1}{2}$。

这道题还有坑点。

• 极少（不）取模。

你想干嘛？？？

• 少取模 $40$。

数据范围这么大还敢不认真取模？？？

$m$ 就不取模了？

• 全取模

谁让你给 $n$ 取模了？

998244354 1000000000000

---

最强数据：

std 200 ms

562949953421312 36028797018963967