Pólya定理 例题

发表于 | 分类于

Pólya定理

先挖个坑 回头慢慢填 前面的太长了(群论基础到转置到polya 好多)

就先从例题说一下吧

例题

SGU 282 同构

题目描述

我们把使得每对顶点都被恰好一条边连接，且被M种不同颜色之一染色的无向图叫做染色图。如果可以把某张染色图的顶点重新编号使得它和另一张染色图完全相同（即每条对应边的颜色都相同），我们就说这两张染色图是同构的。
给你$N,M$和素数$P$。你需要找到有N个顶点的两两互不同构的染色图数量。输出这个数模P的值。

输入格式

输入一行三个整数$N,M,P(1<=N<=53,1<=M<=1000,P$是素数且$P<=10^6)$。

输出格式

输出一行一个正整数，即互不同构的染色图数量模P的值。

样例输入

sample 1:

1 1 2

sample 2:

3 2 97

sample 3:

3 4 97

样例输出

sample 1:

1

sample 2:

4

sample 3:

20

题解

$n$个点的图有$n!$个置换，枚举肯定不可能的所以可以把$n$分解成若干个环，那么剩下的多于计算的就可以省去了那么不同环上的$a，b$两点，显然轮换个数为$gcd(n_a,n_b)$然后套polya即可
#uncomplete

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 1111
typedef long long ll;
ll num[maxn],cnt[maxn],res,factor[maxn],n,m,p,ans;
void init()
{
    ans=res=0;
    factor[0]=1;
    for(int i=1;i<maxn;i++)
        factor[i]=factor[i-1]*i%p;
}
ll gcd(ll a,ll b)
{
    if(a<b)return gcd(b,a);
    if(b==0)return a;
    return gcd(b,a%b);
} 
ll mod_pow(ll a,ll b,ll p)
{
    ll ans=1ll;
    a%=p;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    } 
    return ans;
}
void dfs(ll now,ll left)
{
    if(left==0)
    {
        ll a=1,b=0;
        for(ll i=0;i<res;i++)
        {
            a=a*mod_pow(num[i],cnt[i],p)%p*factor[cnt[i]]%p;
            b+=cnt[i]*(cnt[i]-1)/2*num[i]+num[i]/2*cnt[i];
            for(ll j=i+1;j<res;j++)
                b+=cnt[i]*cnt[j]*gcd(num[i],num[j]);
        }
        a=mod_pow(a,p-2,p)*factor[n]%p;
        ans=(ans+a*mod_pow(m,b,p)%p)%p;
    }
    if(now>left)return ;
    dfs(now+1,left);
    for(ll i=1;i*now<=left;i++)
    {
        num[res]=now,cnt[res++]=i;
        dfs(now+1,left-i*now);
        res--;
    }
}
int main()
{
    while(~scanf("%lld%lld%lld",&n,&m,&p))
    {
        init();
        dfs(1,n);
        ans=ans*mod_pow(factor[n],p-2,p)%p;
        printf("%lld\n",ans);
    }
    return 0;
}