置换群是弱项.

Description

$n$个点, 本质不同的完全图有多少个.

Solution

可以把$n \choose 2$的每条边视为黑/白, 也就是给完全图做染色了.

但本题的同构定义在点的置换上, 我们需要做一些转化.

考虑一个长为$x$的点循环节, 再考虑一条边, 如果两端都在这个循环节里, 那么这条边经过$x$轮就会回到原处(不考虑对称轴). 也就是一个循环途径了$x$条边.

所以这样产生的边循环节有$\frac{x \choose 2}{x}$个. 大概是$\frac{2}{x}$. 偶数循环还要讨论一下对称轴.

然后考虑一下不在同一循环节内的边是怎么被置换的, 一条横跨两个循环节的边, 一定经过$lcm(x,y)$轮回到开始, 对于所有横跨这两个循环节的边来说, 就有$\frac{xy}{lcm(x,y)}$个边循环节了, 也就是$gcd(x,y)​$.

根据Polya就有本质不同的染色方案$\frac{1}{N!}\sum{2^{m}}$, 其中$m$是每种置换的边循环节个数.

我们有点置换和边置换是一一对应的, 所以用枚举点置换的方法(枚举拆分)就可以算了.

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
#include <bits/stdc++.h>
#define mod 997

using namespace std;

const int maxn = 61;

typedef long long ll;

int n;
int val[maxn], num[maxn], cnt;
ll fac[maxn], ans, inv[maxn], facinv[maxn], bin[maxn];

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}
void init() {
  fac[0] = fac[1] = 1; inv[1] = 1;
  facinv[0] = facinv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    fac[i] = (fac[i - 1] * i) % mod;
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    facinv[i] = facinv[i - 1] * inv[i] % mod;
  }
}
inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % mod;
    index >>= 1;
    base = base * base % mod;
  }
  return ret;
}
void dfs(int curNum, int left) {
  if (!left) {
    ll loopCount = 0, permCount = 1;
    for (int i = 1; i <= cnt; ++i) {
      loopCount += (num[i] * (num[i] - 1) / 2 * val[i]) + (val[i] / 2 * num[i]);
      for (int j = i + 1; j <= cnt; ++j) {
        loopCount += num[i] * num[j] * gcd(val[i], val[j]);
      }
    }
    for (int i = 1; i <= cnt; ++i) {
      permCount = permCount * quick_power(val[i], num[i]) % mod * fac[num[i]] % mod;
    }
    permCount = quick_power(permCount, mod - 2) * fac[n] % mod;
    ans = (ans + quick_power(2, loopCount) * permCount % mod) % mod;
    return;
  }
  if (curNum > left) return;
  dfs(curNum + 1, left);
  for (int i = 1; i * curNum <= left; ++i) {
    val[++cnt] = curNum; num[cnt] = i;
    dfs(curNum + 1, left - i * curNum);
    --cnt;
  }
}

int main() {
  scanf("%d", &n);
  init();
  dfs(1, n);
  ans = ans * facinv[n] % mod;
  printf("%lld\n", ans);
  return 0;
}