[PHP知识库]群论习题集

1.hdoj多校 项链染色
3种颜色，相邻颜色不同，绿色不超过k种。
mlgbd莫比乌斯函数整半天发现整错了，整对ac之后，发现暴力求gcd两个跑不满的log也能过就很离谱了。
所以大致思路就是burnsid定理，找每种置换的不动点。
那么其实哈，对于项链转动k这个置换，其下的不动点相当于对长度gcd(k, n)这玩意求不转的不动点。
这玩意其实可以暴力求，大致思路就是对于有i个绿色的话（记gcd(k,n)=a）那么此时染色法就是$C_{a?i?1}^{i?1}$，暴力求的时候注意是否满足少于k种。
然后统计gcd个数即可，这个暴力和容斥都能过。
题解说的什么反演属实懒得看，逆天。
https://acm.hdu.edu.cn/showproblem.php?pid=6960

#include<bits/stdc++.h>
using namespace std;
#define N 1000009
#define LL long long
#define INF 0x3f3f3f3f
const int K = 998244353;
LL inv[N], jie[N], inj[N], tw[N], miu[N], mark[N];
void init(){
    tw[0] = 1;
    for(int i = 1; i < N; i++) tw[i] = 1ll * tw[i - 1] * 2 % K;
    inv[1] = 1;
    for(int i = 2; i < N; i++)
        inv[i] = 1ll * (K - K / i) * inv[K % i] % K;
    jie[0] = 1;
    for(LL i = 1; i < N; i++) jie[i] = 1ll * i * jie[i - 1] % K;
    inj[0] = 1;
    for(int i = 1; i < N; i++) inj[i] = 1ll * inv[i] * inj[i - 1] % K;
    for(int i = 1; i < N; i++) miu[i] = 1;
    for(int i = 2; i < N; i++){
        if(mark[N]) continue;
        miu[i] = -1;
        for(int j = 2; j * i < N; j++){
            mark[i * j] = 1;
            if(j % i == 0) miu[j * i] = 0;
            else miu[j * i] *= -1;
        }
    }
}
int C(int m, int n){
    return (1ll * jie[n] * inj[m] % K * inj[n - m]) % K;
}
void solve(){
    // cout << "round begin" << endl;
    LL n, k, ans = 0; cin >> n >> k;
    if(k > n) k = n;
    for(LL i = 2; i <= n; i++){
        if(n % i != 0) continue;
        LL cnt = 0;
        LL d = n / i;
        for(LL j = 1; j <= d; j++){
            // cnt += miu[j] * d / j;
            if(__gcd(j, d) == 1) cnt++;
        }
        if(!(i & 1)) ans = (ans + 2 * cnt) % K;
        for(LL j = 1; d * j <= k && j * 2 <= i; j++){
            ans = (ans + (((1ll * C(j - 1, i - j - 1) * tw[j] % K) * i % K) * inv[j] % K) * cnt) % K;
        }
    }
    ans = 1ll * ans * inv[n] % K; ans = (ans + K) % K;
    cout << ans << endl;
}
int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
    init();
    int T; cin >> T;
    while(T--) solve();
	return 0;
}