$\color{green}{\mathrm{置换群}}$
$\color{green}{\mathrm{polya定理}}$
设$G$是$p$个对象的一个置换群,用$k$个颜色去染这$p$个对象,若一种染色方案在群$G$的作用下变为另一种方案,则这两种方案当作同一种方案,这样不同的染色方案为:$L=\frac{1}{|G|}\times\sum(k^{C(f)}), f\in G$,$C(f)$ 为循环节,$|G|$是置换方法数
$polya$定理用更加好理解方式表述就是染色的实质方案数就是每一种置换的不动点个数的平均值,其中每种置换不 动 点个数等于颜色数的循环节个数次方
具体样例
对于有$n$个位置的手镯,有n种旋转置换和那种翻转置换
对于旋转置换:
$C(f_i)=gcd(n,i)$,其中i表示一次转过i颗宝石,$i=0$是$c=n$
对与翻转置换:
如果$n$是偶数:则有$\frac n2$个置换$C(f)=\frac n2$,$\frac n2$个置换$C(f)=\frac n2 +1$
如果$n$是奇数: $C(f)=\frac n2+1$
$\color{green}{\mathrm{burnside引理}}$
$burnside引理$与$polya定理$的区别在于你要自己判断每种置换的不动点个数
例题:魔法手链
分析:对于每一种旋转置换都可以分成$d=gcd(n,k)$个置换环,每个置换环中珠子的颜色都市相同的,所以问题就变成了一段长度为$d$的环用$k$种颜色染色可以得到的方案个数,这可以dp求出,同时需要对旋转置换分类
// CREATED BY MASHIROYUKI
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize("O3")
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
}
typedef long long ll;
typedef double db;
const int mod = 9973;
const int N = 1e6 + 10;
ll n,m,k;
struct matrix {
ll mt[11][11];
matrix() {memset(mt,0,sizeof mt);}
matrix operator*(matrix&o) {
matrix c;
rep(i,1,m)
rep(j,1,m)
rep(k,1,m)
c.mt[i][j]=(c.mt[i][j]+mt[i][k]*o.mt[k][j]%mod)%mod;
return c;
}
};
ll phi(int x) {
int up=sqrt(x+0.),res=x;
rep(d,2,up) if(!(x%d)) {
res=res/d*(d-1);
while(!(x%d)) x/=d;
}
if(x!=1) res=res/x*(x-1);
return res;
}
ll inv(int x) {
ll res=1,k=mod-2;
x%=mod;
for(;k;k>>=1,x=(__int128)x*x%mod)
if(k&1) res=(__int128)res*x%mod;
return res;
}
ll dp(matrix x,int k) {
matrix res;
rep(i,1,m) res.mt[i][i]=1;
for(;k;k>>=1,x=x*x)
if(k&1) res=res*x;
ll t=0;
rep(i,1,m) t=(t+res.mt[i][i])%mod;
return t%mod;
}
void solve()
{
read(n),read(m),read(k);
matrix base;
rep(i,1,m) rep(j,1,m) base.mt[i][j]=1;
rep(i,1,k) {
int x,y;
read(x),read(y);
base.mt[y][x]=base.mt[x][y]=0;
}
ll up=sqrt(n+0.),res=0;
rep(d,1,up) if(!(n%d)) {
res=(res+phi(d)*dp(base,n/d)%mod)%mod;
if(d!=n/d) res=(res+phi(n/d)*dp(base,d)%mod)%mod;
}
printf("%lld\n",res*inv(n)%mod);
}
signed main()
{
//IO
int t;
read(t);
while(t--) solve();
return 0;
}