题解：AT_abc428_g [ABC428G] Necklace

分享一种比较暴力的做法。

首先肯定是使用 Burnside 引理求解，不过题目并没有给定环的大小，但是由于大小为 \(n\) 的环至少要有 \(2^n\) 的美丽值，所以这个 \(n\) 只有 \(\log m\) 个。

所以可以快乐的枚举环的大小，假设是 \(n\)。

那么要求：

\[\sum_{i = 0}^{n - 1}{f(g_i)} \]

\(g_i\) 表示将环顺时针转 \(i\) 下，\(f(g_i)\) 表示在 \(g_i\) 作用下不变的环的个数。

将环上一个点向转完后的位置连边，会连出 \(\gcd(n, i)\) 个环，并且这些环内的颜色必须一样，再满足美丽值之积为 \(x\)。

先将 \(a_k\) 变为 \(a_k^{\frac{n}{\gcd(n, i)}}\)。

此时设 \(h(i)\) 表示 \(i\) 出现的次数，\(dp_{i, j}\) 表示 \(i\) 个数乘积为 \(j\) 的方案数。

转移为：

\[dp_{i, j} = \sum_{d | j}{h(\frac{j}{d})\times dp_{i - 1, d}} \]

如果设 \(F * G\) 表示两者的狄利克雷卷积，就有：

\[dp_i = dp_{i - 1} * h = h^i \]

\(x\) 的答案就是 \(dp_{\gcd(n, i)}\) 的第 \(x\) 项。

这样长度为 \(n\) 的答案就是 \(\sum_{i = 0}^{n - 1}{h^{\gcd(n, i)}}\)。

不过复杂度有点劣，改为枚举 \(gcd(n, i)\)，答案变成 \(\sum_{d | n}{h^d \varphi(\frac{n}{d})}\)。

总答案为：

\[\sum_{n = 1}^{\log m}{\sum_{d | n}{h^d \varphi(\frac{n}{d})}} \]

注：此处 \(h\) 随着 \(n\) 和 \(d\) 变化。

分析一下复杂度，这两个求和是 \(\mathcal{O}(\sqrt{\log m}\log m)\) 的，卷积使用快速幂会进行 \(\log{\log m}\) 次卷积，一次卷积是 \(\mathcal{O}(m \log m)\) 的。

所以复杂度是 \(\mathcal{O}(m\sqrt{\log m}\log^2 m\log{\log m})\) 的，常数比较小。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 5e5 + 10, mod = 998244353;#define int long long#define fi first
#define se secondusing pii = pair <int, int>;int n, m, a[N];class Poly
{public :int f[N];friend Poly operator * (Poly x, Poly y){Poly res;for (int i = 1; i <= m; i++) res.f[i] = 0;for (int i = 1; i <= m; i++){if (!x.f[i]) continue;for (int j = 1; j <= m / i; j++){(res.f[i * j] += x.f[i] * y.f[j]) %= mod;}}return res;}
};Poly qpow(Poly x, int b)
{Poly res;for (int i = 1; i <= m; i++) res.f[i] = 0;res.f[1] = 1;while (b){if (b & 1) res = res * x;x = x * x;b >>= 1;}return res;
}int qpow(int x, int b, int lim)
{int res = 1;while (b){if (b & 1){if (x > lim) return false;res = res * x;if (res > lim) return false;}if (x <= lim) x = x * x;b >>= 1;}return res;
}int qpow(int x, int b)
{int res = 1;while (b){if (b & 1) res = res * x % mod;x = x * x % mod;b >>= 1;}return res;
}int phi(int x)
{int res = x;for (int i = 2; i * i <= x; i++){if (x % i) continue;res = res / i * (i - 1);while (x % i == 0) x /= i;}if (x != 1) res = res / x * (x - 1);return res;
}int ans[N];
Poly F;signed main()
{ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);int lim = 0;while ((1 << lim) <= m) lim++;for (int _n = 1; _n <= lim; _n++){bool flag = 0;for (int i = n; i >= 1; i--) if (qpow(a[i], _n, m)) flag = 1;if (!flag) break;int inv = qpow(_n, mod - 2);for (int i = 1; i <= _n; i++){if (_n % i) continue;for (int j = 1; j <= m; j++) F.f[j] = 0;for (int j = 1; j <= n; j++) F.f[qpow(a[j], _n / i, m)]++;Poly tmp = qpow(F, i);int ph = phi(_n / i);for (int j = 2; j <= m; j++) (ans[j] += tmp.f[j] * ph % mod * inv) %= mod;}}for (int i = 2; i <= m; i++) cout << ans[i] << ' ';return 0;
}