题意
如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。
如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。
对于计算所有顶点数为 (n) ，颜色种类不超过 (m) 的图，最多有几张是两两不同构的图。
数据范围
(n le 53, 1 le m le 1000)
题解
神仙题qwq
我们考虑对于点置换与其对应的边置换的关系：
-
对于不处在循环中的点对：
假设第一个循环长度为 (l_1) 第二个循环长度为 (l_2) ，那么循环节长度就是 (mathrm{lcm}(l_1, l_2)) 。
一共有 (l_1 imes l_2) 对点对，每个点对所处的循环节长度都是一样的，那么循环节个数就是 (displaystyle frac{l_1l_2}{mathrm{lcm}(l_1, l_2)} = gcd(l_1, l_2)) 。
-
对于处在循环中的点对：
设循环长度为 (l) ，分奇偶讨论。
- (l) 为奇数，那么循环长度刚好是 (l) ，一共有 (displaystyle {l choose2}) 对点对，那么刚好就有 (displaystyle frac{l - 1}2) 个循环节。
- (l) 为偶数，上面那种情况之外，还有转 (displaystyle frac l2) 长度对应的循环节，那么一共有 (displaystylefrac{ {l choose 2} - frac l2}{l} + 1 = frac l2) 个循环节。
设一开始点置换划分的周期为 (l_1 le l_2 le cdots le l_k) ，其中满足 (sumlimits _{i = 1}^{k} l_i = n) 。
那么循环节的个数其实就是：
我们显然可以枚举所有 (l) 的集合，不难发现这就是整数划分，(53) 的划分数并不大。。。
只剩下最后一个问题，就是有多少个长为 (n) 的排列对应到 (l_1 cdots l_k) 这个点置换循环。
首先考虑可重排列计数，把 (n) 个数分给这些的方案为 (displaystyle frac{n!}{prod_{i=1}^{k} l_i!}) 然后对于每个置换 (i) 内部是个圆排列，顺序有 ((l_i - 1)!) 。然后循环的先后顺序是互不影响的，要除掉 (c_i! (c_i = sum_{j = 1}^{n}[l_j = i])) 个。
也就是
总结
对于 (Polya) 定理，常常要找循环节个数。对于特殊的置换，我们常常可以利用循环长度是一样的性质，然后用总元素 (/) 循环长度，得到循环节个数。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("1815.in", "r", stdin);
freopen ("1815.out", "w", stdout);
#endif
}
const int N = 65;
int n, m, Mod;
int cir[N], len, ans = 0;
inline int fpm(int x, int power) {
int res = 1;
for (; power; power >>= 1, x = 1ll * x * x % Mod)
if (power & 1) res = 1ll * res * x % Mod;
return res;
}
void Dfs(int cur, int rest, int res) {
if (!rest) {
int coef = 1, cnt = 1;
For (i, 1, len) {
if (cir[i] != cir[i - 1]) cnt = 1; else ++ cnt;
coef = 1ll * coef * cnt % Mod * cir[i] % Mod;
}
ans = (ans + 1ll * fpm(m, res) * fpm(coef, Mod - 2)) % Mod; return;
}
For (i, cur, rest) {
int tmp = i / 2; For (j, 1, len) tmp += __gcd(i, cir[j]);
cir[++ len] = i; Dfs(i, rest - i, res + tmp); -- len;
}
}
int main () {
File();
n = read(); m = read(); Mod = read();
Dfs(1, n, 0);
printf ("%d
", ans);
return 0;
}