题目大意
有一个由 (n) 个珠子组成的项链,珠子有红绿蓝三种颜色,要求项链中相邻的珠子不能同色,求绿色珠子数量不超过 (k) 的本质不同项链的总数。若两条项链能通过顺时针旋转变得相同,则认为这两条项链本质相同。(1leq n,kleq 10^**6)
题解
考虑 Burnside 引理:
设 (g(n,m)) 表示对长度为 (n) 的环进行染色,在绿色的个数为 (m) 的情况下,染色的方案数(不考虑本质不同)。当顺时针旋转 (i) 步时,圆环被划分为 (mathrm{gcd}(n,i)) 段,每一段的长度均为 (frac{n}{mathrm{gcd}(n,i)}),每一段内的点颜色必须相同,只有这样,顺时针旋转 (i) 步后圆环才和初始时相同。所以此时要么整个段全为绿色,要么整个段全不为绿色。那么顺时针旋转 (i) 步时和原来相同的染色方案数为
而对于一个 (n) 个点的圆环,一共有 (n) 个置换,由Burnside引理,有:
考虑怎么求 (g(n,m)),即长度为 (n) 的圆环,有 (m) 个点是绿色,不考虑本质不同的涂色方案数。
假设我们已经在 (m) 个不相邻的点涂了绿色,在绿色点的间隙中,要么"红蓝红...",要么"蓝红蓝..."这样涂色,一共有 (m) 个间隙,如果已经确定了绿色的涂色方案,也即确定了每个间隙的长度,每个间隙中只有两种涂其他颜色的方案,那么涂其他颜色的方案数为 (2^m),还要乘上一个涂绿色点的方案数,即为 (g(n,m))。而涂绿色点的方案数等于在长度为 (n) 的圆环上选取 (m) 个不相邻的点的方案数,若 (n) 号点已经被涂成绿色,则剩下 (n-m-1) 个位置要插入 (m-1) 个绿色点,方案数为 (inom{n-m-1}{m-1});若不把 (n) 号点涂成绿色,则剩下 (n-m) 个位置要插入 (m) 个绿色点,方案数为 (inom{n-m}{m})。所以 (g(n,m)=2^mleft[inom{n-m}{m}+inom{n-m-1}{m-1} ight],m eq 0)。当 (m=0) 时,若 (n) 为奇数,(g(n,0)=0),若 (n) 为偶数,(g(n,0)=2)。
再考虑答案的式子,先枚举 (mathrm{gcd}),有
其中
我们可以预处理出阶乘和阶乘的逆元来快速计算组合数。对于每一个 (n) 的因子 (d),计算出 (F(d)),然后累加即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define RG register int
#define LL long long
const LL MOD = 998244353LL;
LL inv[1000010], fact[1000010], finv[1000010], two[1000010];
int Phi[1000005];
bool not_Prime[1000005];
vector<int> Prime;
void Init() {
inv[1] = fact[0] = fact[1] = finv[0] = finv[1] = two[0] = 1;
two[1] = 2;
for (int i = 2;i <= 1000000;++i) {
inv[i] = ((-(MOD / i) * inv[MOD % i]) % MOD + MOD) % MOD;
fact[i] = fact[i - 1] * i % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
two[i] = (two[i - 1] << 1) % MOD;
}
}
LL C(int n, int m) {
if (m > n) return 0;
return fact[n] * finv[m] % MOD * finv[n - m] % MOD;
}
void Get_Phi(int Len) {
not_Prime[1] = true;
Phi[1] = 1;
int Count = 0;
for (int i = 2;i <= Len;i++) {
if (!not_Prime[i]) { Prime.push_back(i);Phi[i] = i - 1; }
for (int j = 0;j < Prime.size();++j) {
int mid = i * Prime[j];
if (mid > Len) break;
not_Prime[mid] = true;
if (i % Prime[j] == 0) { Phi[mid] = Phi[i] * Prime[j];break; }
Phi[mid] = Phi[i] * (Prime[j] - 1);
}
}
}
int T, n, k;
inline LL g(int d, int i) {
if (i == 0) {
if (d & 1) return 0;
return 2;
}
return two[i] * (C(d - i, i) + C(d - i - 1, i - 1)) % MOD;
}
LL F(int d) {
LL res = 0;
for (int i = 0;i <= (1LL * k * d) / n;++i)
res = (res + g(d, i)) % MOD;
return res;
}
int main() {
Init();
Get_Phi(1000000);
cin >> T;
while (T--) {
cin >> n >> k;
int d;LL ans = 0;
for (d = 1;d * d < n;++d) {
if (n % d == 0) {
ans = (ans + Phi[n / d] * F(d) % MOD) % MOD;
ans = (ans + Phi[d] * F(n / d) % MOD) % MOD;
}
}
if (d * d == n) ans = (ans + Phi[d] * F(d) % MOD) % MOD;
ans = ans * inv[n] % MOD;
printf("%lld
", ans);
}
return 0;
}