## 【算法笔记】Burnside引理与Pólya定理

### 前言

hht真的好神啊！伏地膜！

hht：“我不用学习也能考很好，我在高一的时候已经把高中内容看完了”

### 正文

hht主要讲了Burnside引理的不完全证明和用Burnside引理推出Pólya定理

##### Burnside引理的不完全证明

$|Z_k| \cdot |E_k| = |G|$

##### 使用Burnside引理推导Pólya定理

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

inline LL pow(int w, int t) {
LL ret = 1;
while (t) {
if (t & 1) ret *= w;
t >>= 1, w *= w;
}
return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){
LL vout = 0; int t = n;
for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n));

if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;}
else {
for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2;
for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2;
}

vout /= t;
printf("%lld\n",vout);
}
return 0;
}


polya的板题，其中置换的循环节先用一下程序算，之后再写程序

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;

int to[MAXN],tag[MAXN],ty,delta,n;

inline int Get_M(){
int ret = 0;
for (int i=1,w;i<=n;i++) if (!tag[i]) {
ret++; w = i;
while (!tag[w]) tag[w] = 1, w = to[w];
} return ret;
}

int main(){
cin>>n>>delta>>ty;
if (ty == 1) {
for (int i=1;i<=n;i++) to[i] = i + delta;
for (int i=1;i<=n;i++) if (to[i] > n) to[i] -= n;
} else {
for (int j=1,i=delta;j<=n;j++,i=++i>n?i-n:i) to[i] = n - i;
} cout<<Get_M();
return 0;
}


#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int col = 3;

inline LL pow(int w, int t) {
LL ret = 1;
while (t) {
if (t & 1) ret *= w;
t >>= 1, w *= w;
}
return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){
if (n == 0) {cout<<0<<endl; continue;}
else {
LL vout = 0; int t = n;
for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n));

if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;}
else {
for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2;
for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2;
}

vout /= t;
printf("%lld\n",vout);
}
}
return 0;
}