burnside定理學習小計

基本概念

• 置換：對一個集合的映射，簡單來說就是重排列。

  一個集合 S S S經過映射 a [ 1.. n ] a[1..n] a[1..n]後得到 S ′ S' S′的即 S ′ [ 1 ] = S [ a [ 1 ] ] , S ′ [ 2 ] = S [ a [ 2 ] ] . . . . S'[1]=S[a[1]],S'[2]=S[a[2]].... S′[1]=S[a[1]],S′[2]=S[a[2]]....

• 不動點：如果一個集合 S S S在通過置換 a a a後生成的 S ′ S' S′與 S S S完全相同，那麼我們就稱 S S S為 a a a的不動點。
• 置換群（這個知識目前我沒有用過）：置換群就是置換組成的集合，需要滿足：

  

Burnside定理

• 集合 S S S和 S ′ S' S′是等價類當且僅當有一種置換群 G G G中有置換 a a a可以由 S S S轉變為 S ′ S' S′.
• 對于一個圓環的染色方案就相當于是循環同構。

• 設 c a c_a ca​為置換 a a a的不動點的個數, L L L為等價類個數。burnside引理就是

  L = c a 1 + c a 2 + c a 3 + . . . + c a g ∣ G ∣ L=\frac{c_{a_1}+c_{a2}+c_{a3}+...+c_{ag}}{|G|} L=∣G∣ca1​​+ca2​+ca3​+...+cag​​

• 看下面的例子以更好地了解。

圓環染色

• 對于一個大小為 n n n的圓環，有 m m m種顔色，問本質不同的染色方案有多少種。即循環同構的算一種。
• 對于一個圓環，有 n n n種置換，構成一個置換群，即向右旋轉1步，2步…n步。
• 那麼對于第i種置換，我們要計算它的不動點的個數。
• 如果在向右旋轉i步後完全一樣的話，那麼從0開始往後跳i步（0~n-1編号），最後會跳回0，這條路徑上的所有位置的顔色都相同。

• 我們可以知道從0開始走多少步後就回來了。

  x ∗ i ≡ 0   ( m o d   n ) − > x ≡ 0 ( m o d   n / g c d ( i , n ) ) x*i\equiv 0\: (mod \:n) ->x\equiv 0(mod\:n/gcd(i,n)) x∗i≡0(modn)−>x≡0(modn/gcd(i,n)).

• 即 n / g c d ( i , n ) n/gcd(i,n) n/gcd(i,n)後回來，那麼就一共有 g c d ( i , n ) gcd(i,n) gcd(i,n)個環，每一個環裡面的所有位置的顔色都是一樣的。
• 那麼對于不動點的個數就顯而易見了： m g c d ( i , n ) m^{gcd(i,n)} mgcd(i,n)。
• 實際上這個就是polya定理

了解or證明

• 考慮一個染色方案被重複算了多少次。
• 一個長度為n的染色方案，它的循環節為c，那麼當跳的步數為c的倍數時，這種染色方案就是不動點，共n/c次計算。

• 再考慮這個染色方案一共有c種循環同構的情況

  例如[abc][abc][abc]，[bca][bca][bca]，[cab][cab][cab]。

  這些在不考慮同構的情況下是都會被算到的。

• 是以一共算了n次。
• 是以最後要除以n。

JZOJ4800.周末晚會

傳送門

N個人圍繞着圓桌坐着，其中一些是男孩，另一些是女孩。你的任務是找出所有合法的方案數，使得不超過K個女孩座位是連續的。循環同構被視作同一種方案。

• 如果沒有k的限制的話，那麼就是burnside的模型。
• 注意到計算不動點的時候隻用考慮到第一個循環節。
• 按照k和循環節大小分類讨論即可。

• DP計算f[i]，表示長度為i，沒有多于連續k個的女孩，簡單容斥一下

  f [ i ] = f [ i − 1 ] ∗ 2 − f [ i − k − 2 ] f[i]=f[i-1]*2-f[i-k-2] f[i]=f[i−1]∗2−f[i−k−2]

• d=循環節大小，首先對于每一個循環節要滿足沒有多于k個，其次考慮收尾相連，枚舉相連的部分有多少個女孩，剩下的用f計算即可。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 2005
#define ll long long
#define mo 100000007
using namespace std;

int T,n,k,i,j,d;
ll f[maxn],sum;

int gcd(int x,int y){return (x%y==0)?y:gcd(y,x%y);}
ll ksm(ll x,ll y){
	ll s=1;
	for(;y;y/=2,x=x*x%mo) if (y&1)
		s=s*x%mo;
	return s;
}

int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&k);
		if (k>=n) {
			sum=0;
			for(i=1;i<=n;i++) sum+=ksm(2,gcd(i,n));
			sum%=mo;
			printf("%lld\n",sum*ksm(n,mo-2)%mo);
			continue;
		}
		memset(f,0,sizeof(f));
		for(f[0]=1,i=1;i<=k;i++) f[i]=f[i-1]*2%mo;
		for(i=k+1;i<=n;i++) f[i]=(f[i-1]*2-((i==k+1)?1:f[i-k-2]))%mo;
		sum=0;
		for(i=1;i<=n;i++){
			d=gcd(i,n);
			if (d<=k) {sum+=ksm(2,d)-1;continue;}
			sum+=f[d];
			for(j=k+1;j<d&&j<=2*k;j++) 
				sum-=((d-j<=2)?1:f[d-j-2])*(k-(j-k)+1)%mo;
		}
		printf("%lld\n",(sum%mo+mo)%mo*ksm(n,mo-2)%mo);
	}
}
           

牛客挑戰賽34 C.遠山的占蔔

傳送門

給2n的圓環染色，一共有m種顔色，循環同構以及對角線位置（即i與i+n）交換後相同的方案視為一種。

共有多少種不同的方案？

T(T<=2222)組資料,n,m<19260817，模19260817

• 将對角線的兩個元素一起看的，那麼一共有m*(m+1)/2種顔色，要塗到n個地方。
• 由于資料比較多，可以枚舉gcd，然後乘phi(n/gcd)即可。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 20000000
#define mo 19260817
#define ll long long 
using namespace std;

int T,i,j,k;
int tot,pri[maxn/10],bz[maxn],phi[maxn];
ll n,m,sum;

ll ksm(ll x,ll y){
	ll s=1;
	for(;y;y/=2,x=x*x%mo) if (y&1)
		s=s*x%mo;
	return s;
}

void GetPhi(){
	phi[1]=1;
	for(i=2;i<maxn;i++){
		if (!bz[i]) pri[++tot]=i,phi[i]=i-1;
		for(j=1;j<=tot&&i*pri[j]<maxn;j++) {
			bz[i*pri[j]]=1;
			if (i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j]%mo;
				break;
			} else phi[i*pri[j]]=phi[i]*(pri[j]-1)%mo;
		}
	}
}

int main(){
	GetPhi();
	scanf("%d",&T);
	while (T--){
		scanf("%lld%lld",&n,&m);
		m=m*(m+1)/2%mo;
		sum=0;
		for(i=1;i<=sqrt(n);i++) if (n%i==0){
			sum+=ksm(m,i)*phi[n/i]%mo;
			if (i*i!=n) sum+=ksm(m,n/i)*phi[i]%mo;
		}
		printf("%lld\n",sum%mo*ksm(n,mo-2)%mo);
	}
}