JSOI2006 同构

本文移植自个人的原博客（原文）

题目描述

我们把使得每对顶点都被恰好一条边连接，且被$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$进行整数拆分的方案数，那么需要枚举的置换便由 $n!$ 降到了 $10^6$以内。

关于取模的问题，已知$p$是质数（这个题应该保证了$P>53$），易证两者互质，则可通过费马小定理求逆。

（当时没系统地接触过群论，还不太理解Polya定理的含义）

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e4+1;
ll num[N],cnt[N],res,fac[N],n,m,p,ans;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} 
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%p;
        b>>=1;a=(a*a)%p;
    }
    return ans;
}
int dfs(ll now,ll maxl)
{
    if(maxl==0)
    {
        ll a=1,b=0;
        for(int i=0;i<res;i++)
        {
            a=a*qpow(num[i],cnt[i])%p*fac[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=qpow(a,p-2)*fac[n]%p;
        ans=(ans+a*qpow(m,b)%p)%p;
    }
    if(now>maxl)return 0;
    dfs(now+1,maxl);
    for(int i=1;i*now<=maxl;i++)
    {
        num[res]=now,cnt[res++]=i;
        dfs(now+1,maxl-i*now);
        res--;
    }
}
int main()
{    
//    freopen("isomorphism.in","r",stdin);
//    freopen("isomorphism.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&p);
    fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;
    dfs(1,n);
    ans=ans*qpow(fac[n],p-2)%p;
    printf("%lld\n",ans);
}