HDU-6960 Necklace of Beads 置换-Burnside引理

HDU-6960 Necklace of Beads 置换-Burnside引理

题意

给长度为(n)的项链涂上红色、蓝、绿三种颜色 并且要求绿色不超过(k)个 任意相邻的也不同色

求本质不同的方案数

分析

那么若用(g(n,k))表示对长度(n)的环染色且绿色个数为(k)的方案数(不要求本质不同)

那么当旋转(i)次后，就可以得到((n,i))个循环节，循环节长度为(frac{n}{(n,i)}) ，且要求每个循环节颜色相同。

同时要么整段都是绿色 要么都不是绿色 那么枚举绿色的个数有

[sum|X^g| =sum_{j = 0}^{frac{k(i,n)}{n}}g((n,i),j) ]

套用Burnside引理

[|X/G| = frac{1}{n}sum_{g in G}|X^g| ]

[ans= frac{1}{n}sum_{i=0}^{n -1}sum_{j=0}^{frac{k(i,n)}{n}}g((n,i),j) ]

考虑(g(n,k))的求法 就是要求任意两个绿色的间隔大于0，间隔之间只有红绿红.. 或者绿红绿... 所以需要乘上(2^k)

而绿色方法就是经典的隔板法 -> 考虑(x_1 + x_2 + ..x_k = n - m)的解即可(x_i > 0) 当然还要注意讨论环带来的影响

那么再进行简单的数论变换

即可得到

[ans = frac{1}{n} sum_{d|n}phi(lfloorfrac{n}{d} floor)sum_{j=0}^{lfloorfrac{kd}{n} floor}g(d,j) ]

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;


ll rd(){
	ll x;
	scanf("%lld",&x);
	return x;
}

const int MOD = 998244353;
const int maxn = 1e6 + 5;

int phi[maxn];
int fac[maxn];
int iv[maxn];

inline void add(int &x,int y){
	x += y;
	if(x >= MOD) x -= MOD;
}


inline int ksm(int a,int b = MOD - 2,int m = MOD){
	int ans = 1;
	int base = a;
	while(b){
		if(b & 1) ans = (ll)ans * base % MOD;
		base = (ll)base * base % MOD;
		b >>= 1;
	}
	return ans;
}

inline int C(int n,int m){
	if(m > n) return 0;
	return (ll)((ll)fac[n] * iv[n - m] % MOD) * iv[m] % MOD;
}

inline int get(int n,int k){
	if(!k) {
		if(n & 1) return 0;
		return 2;
	}
	return (C(n - k,k) + C(n - k - 1,k - 1)) % MOD;
}

int _2[maxn];

inline int add(int k,int d,int n){
	int ans = 0;
	int lim = (ll)k * d / n;
	for(int i = 0;i <= lim;i++){
		add(ans,(ll)_2[i] * get(d,i) % MOD);
	}
	return ans;
}


int main(){
	phi[1] = 1;
	for(int i = 2;i < maxn;i++){
		if(!phi[i]) {
			for(int j = i;j < maxn;j += i){
				if(!phi[j]) phi[j] = j;
				phi[j] = (ll)phi[j] / i * (i - 1);
			}
		}
	}
	fac[0] = 1;
	iv[0] = ksm(1);
	_2[0] = 1;
	for(int i = 1;i < maxn;i++)
		fac[i] = (ll)fac[i - 1] * i % MOD,_2[i] = (ll)_2[i - 1] * 2 % MOD,iv[i] = ksm(fac[i]);
	int T = rd();
	while(T--){
		int ans = 0;
		int n = rd();
		int k = rd();
		for(int i = 1;i * i <= n;i++){
			if(n % i) continue;
			add(ans,(ll)phi[n / i] * add(k,i,n) % MOD);
			if(i * i == n) break;
			add(ans,(ll)phi[i] * add(k,n / i,n) % MOD);
		}
		ans = (ll)ans * ksm(n) % MOD;
		printf("%d
",ans);
	}
}