820 字
4 分钟
BZOJ1478/1815 Sgu282 Isomorphism/[Shoi2006]color 有色图
Description
给 定一个个结点的无向完全图( 任意两个结点之间有一条边), 现在你可以用 种颜色对这个图的每条边进行染色,每条边必须染一种颜色。 若两个已染色的图,其中一个图可以通过结点重新编号而与另一个图完全相同, 就称这两个染色方案相同。 现在问你有多少种本质不同的染色方法,输出结果 。 是一个大于的质数。
Input
仅一行包含三个数,、、。
Output
仅一行,为染色方法数 的结果。
Sample Input
3 4 97
Sample Output
20
题解
假定一个点置换,把它表示为循环,比如是
- 对于不在一个循环里面的点: 比如, 那么会有边循环设循环的循环节是循环的循环节是,那么形成的边循环的循环节显然是。一共有个点对,每个点对都在一个循环节为的循环上,所以一共有个循环节,所以。(回到引理,为置换之后仍为本身的数目,就是说要循环节里的每条边都一样的颜色)
- 对于在一个循环里面的点: 比如、。设这个循环的循环节为。
- 如果是奇数,那么循环长度为,一共有个点对,所以是个循环节,所以。
- 如果是偶数,除了上面这种情况之外,还有一种的循环节是(就是两个点刚好相隔半个周期,而边是双向的),所以一共有个点对。
整理一下:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int MOD;const int MAXN = 1005;int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);}int gd[MAXN][MAXN], f[MAXN];long long pow_mod(long long a, int b){ long long ans = 1; while (b) { if (b & 1) ans = ans * a % MOD; b >>= 1; a = a * a % MOD; } return ans;}int l[MAXN];long long ans;int n, m;void Get_Ans(int cnt){ long long C = 0; for (int i = 1; i <= cnt; i++) C = (C + l[i] / 2) % MOD; for (int i = 1; i <= cnt; i++) for (int j = i + 1; j <= cnt; j++) C = (C + gd[l[i]][l[j]]) % MOD; long long now = 1, len = 0; for (int i = 1; i <= cnt; i++) { if (l[i] != l[i - 1]) { now = now * f[len] % MOD; len = 0; } len++; } now = now * f[len] % MOD; for (int i = 1; i <= cnt; i++) now = now * l[i] % MOD; long long S = f[n] * pow_mod(now, MOD - 2) % MOD; ans = (ans + S * pow_mod(m, C) % MOD) % MOD;}void DFS(int cnt, int x, int les){ if (les == 0) return Get_Ans(cnt); if (les < x) return; cnt++; while (x <= les) { l[cnt] = x; DFS(cnt, x, les - x); x++; }}int main(){ n = read(), m = read(); MOD = read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) gd[i][j] = gcd(i, j); 0[f] = 1; for (int i = 1; i <= n; i++) i[f] = 1ll * ((i - 1)[f]) * i % MOD; ans = 0; DFS(0, 1, n); printf ("%lld\n", ans * pow_mod(f[n], MOD - 2) % MOD);}
BZOJ1478/1815 Sgu282 Isomorphism/[Shoi2006]color 有色图
https://www.nekomio.com/posts/135/