HNOI2009 图的同构记数

标签： 数学 置换 polya定理

---

题目描述

小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。A图与B图被认为是同构的是指：A图的顶点经过一定的重新标号以后，A图的顶点集和边集要完全与B图一一对应。
小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含N个点的图有多少种。众所周知含N个点的简单图最多有$\frac{n(n-1)}{2}$条边，这样含N个点的图有$2^{\frac{n(n-1)}{2}}$种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！

输入输出格式

输入格式：
从文件input.txt中读入数据，文件中只有一个非负整数N，表示图的顶点数，且0≤N≤600。

输出格式：
输出文件output.txt中仅包含一个整数，表示含N个点的图在同构意义下不同构的图的数目。因为答案可能很大，所以输出的最终答案是mod997的结果（997是一个素数）。

输入输出样例

输入样例#1：
3
输出样例#1：
4

输入样例#2：
5
输出样例#2：
34

输入样例#3：
9
输出样例#3：
493

题解

这道题和SHOI2006 有色图是一样滴，我们可以把两点连不连边想象成染成黑色与白色的关系，剩下的都一样啦~~

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define N 70
#define p 997
#define debug system("pause")
using namespace std;

ll n, m;
ll num[N], d[N];
ll fac[N], ans = 0;

ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}

ll pow_mul(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

void calc(int cnt)
{
    memset(num, 0, sizeof(num));
    ll mul = 1; ll c = 0;
    for(int i = 1; i <= cnt; i ++) 
    {
        num[d[i]] ++;
        mul = mul * d[i] % p;
        c += d[i] / 2;
        for(int j = 1; j < i; j ++)
            c += gcd(d[i], d[j]);
    }
    for(int i = 1; i <= n; i ++) 
        mul = mul * fac[num[i]] % p;
    ans = ans + (pow_mul(mul, p - 2) * pow_mul(m, c) % p);
    ans %= p;            
}

void dfs(int tot, int cnt, int pre)
{
    d[cnt] = tot; 
    calc(cnt);
    for(int i = pre; i <= tot - i; i ++)
    {
        d[cnt] = i;
        dfs(tot - i, cnt + 1, i);
    } 
}

int main()
{
    scanf("%lld", &n); m = 2;
    fac[0] = fac[1] = 1;
    for(int i = 2; i <= n; i ++) fac[i] = fac[i - 1] * i % (ll)p;
    dfs(n, 1, 1);
    printf("%lld", ans);
    return 0;
} 

心得

模型转换很重要啊