BZOJ1815 [Shoi2006]color 有色图

一道burnside，做了几次之后感觉比较经典了。然后发现网上居然没有题解。

枚举正整数拆分，既每个质换的长度。然后枚举gcd算每类置换的贡献。再用错排公式来算每类置换的数量。然后求和。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define _l (long long int)

const int maxn = 63;

int n, m, mod, ans, g[maxn][maxn];
int sq[maxn], tq, fac[maxn], finv[maxn], vinv[maxn];

int modPow(int a, int x) {
	int s(1);
	for (; x; x >>= 1, a = _l a * a % mod)
		if (x & 1)
			s = _l s * a % mod;
	return s;
}

int gcd(int a, int b) {
	while (a) {
		register int c(b % a);
		b = a;
		a = c;
	}
	return b;
}

void addAns() {
	int t(0);
	for (int i = 1; i <= tq; ++ i) {
		t += sq[i] >> 1;
	//	if (sq[i] > 1)
	//		++ t;
		for (int j = 1; j < i; ++ j)
			t += g[sq[i]][sq[j]];
	}
	t = modPow(m, t);
	for (int i = 1, j; i <= tq; i = j) {
		for (j = i; j <= tq && sq[i] == sq[j]; ++ j)
			t = _l t * vinv[sq[j]] % mod;
		t = _l t * finv[j - i] % mod;
	}
	ans = (ans + t) % mod;
}

void dfs(int v, int l) {
	if (!v)
		addAns();
	else {
		++ tq;
		for (int i = 1; i <= l && i <= v; ++ i) {
			sq[tq] = i;
			dfs(v - i, i);
		}
		-- tq;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d%d", &n, &m, &mod);
	fac[0] = finv[0] = 1;
	for (int i = 1; i <= n; ++ i) {
		fac[i] = _l fac[i - 1] * i % mod;
		finv[i] = modPow(fac[i], mod - 2);
		vinv[i] = modPow(i, mod - 2);
		for (int j = 1; j <= n; ++ j)
			g[i][j] = gcd(i, j);
	}
	tq = 0;
	dfs(n, n);
	printf("%d\n", ans);
}