洛谷P4727 [HNOI2009] 图的同构计数 题解

题目链接：P4727 [HNOI2009] 图的同构计数

题意：

小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。\(A\)图与\(B\)图被认为是同构的是指：\(A\)图的顶点经过一定的重新标号以后，\(A\)图的顶点集和边集要完全与\(B\) 图一一对应。

小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含\(N\)个点的图有多少种。众所周知含\(N\)个点的简单图最多有 \(\frac{N(N-1)}{2}\) 条边，这样含\(N\)个点的图有 \(2^{\frac{N(N-1)}{2}}\) 种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！

输入格式：

从文件input.txt中读入数据，文件中只有一个非负整数\(N\)，表示图的顶点数。

输出格式：

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

数据范围：

对于 \(100 \%\) 的数据，\(0 \le N \le 60\)。

可以认为就是对 \(n\) 个点的完全图进行染色，颜色有两种，表示这条边存在/不存在

那么这道题就变成了 \(m=2\) 的完全图的本质不同的染色，详见 洛谷P4128 [SHOI2006] 有色图 题解

时间复杂度 \(\displaystyle \mathcal{O}\left(\log n \sum_{p \in \operatorname{Partition}(n)} \operatorname{len}^2(p)\right)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(75))

int m, p, res, inv[N], fac[N], infac[N];
void add(int &x, int y) { (x += y) >= p ? x -= p : 0; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int qpow(int a, int b)
{
    int r = 1;
    for(; b; b >>= 1, a = a * a % p)
        if(b & 1) r = r * a % p;
    return r;
}
int n1, n2 = 1, top, stk[N];
void init(int n)
{
    inv[1] = fac[0] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;
    infac[n] = qpow(fac[n], p - 2);
    for(int i = n; i; i--) infac[i - 1] = infac[i] * i % p;
}
void dfs(int s, int mx, int c)
{
    if(!s) return add(res, qpow(m, n1) * n2 % p), void(0);
    int a = n1, b = n2;
    for(int i = 1; i <= mx; --top, i++)
    {
        stk[++top] = i; n1 = a + i / 2;
        for(int j = 1; j < top; j++) n1 += gcd(stk[j], i);
        n2 = b * inv[i] % p;
        if(i == stk[top - 1]) n2 = n2 * fac[c] % p * infac[c + 1] % p;
        dfs(s - i, min(s - i, i), i == stk[top - 1] ? c + 1 : 1);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; m = 2, p = 997;
    init(n + 5); dfs(n, n, 0); cout << res << '\n';
    return 0;
}