「bzoj1478」「SGU282」Isomorphism - Polya计数+数论 | Bill Yang's Blog

「bzoj1478」「SGU282」Isomorphism - Polya计数+数论

题目大意

    给定一个$N$个结点的无向完全图(任意两个结点之间有一条边), 现在你可以用$M$种颜色对这个图的每条边进行染色,每条边必须染一种颜色。若两个已染色的图,其中一个图可以通过结点重新编号而与另一个图完全相同, 就称这两个染色方案相同。现在问你有多少种本质不同的染色方法,输出结果$\bmod P$。$P$是一个大于$N$的质数。


题目分析

这道题显然要用Polya计数解决等价类问题。

不妨参考隔壁CQzhangyu大爷的题解,写的很详细我就懒得说了。

不过其例子少打了换行(我才不会告诉你我盯着它看了半个小时这是什么玩意儿):

关于其题解中循环的长度,画画图即可知道了。
另外,因为是循环,循环可以轮换一下意义相同,所以需要乘$(L_1-1)!(L_2-1)!…(L_K-1)!$而不是$L_1!L_2!…L_K!$。


代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=55;
int n,a[maxn],G[maxn][maxn];
LL m,p,Pow[maxn*maxn+maxn],fac[maxn],inv[maxn],invf[maxn],ans=0;
int gcd(int a,int b) {return b==0?a:(G[a][b]?G[a][b]:G[a][b]=gcd(b,a%b));}
void Dfs(int dep,int sum,int last) {
if(!sum) {
LL s=fac[n],c=0,len=0;
for(int i=1; i<=dep; i++) {
len++;
if(i==dep||a[i]!=a[i+1])s=s*invf[len]%p,len=0;
s=s*inv[a[i]]%p;
c+=a[i]>>1;
for(int j=1; j<i; j++)c+=gcd(a[i],a[j]);
}
ans=(ans+Pow[c]*s)%p;
return;
}
for(int i=min(sum,last); i>=1; i--)a[dep+1]=i,Dfs(dep+1,sum-i,i);
}
int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
Pow[0]=1;
for(int i=1; i<=n*n+n; i++)Pow[i]=Pow[i-1]*m%p;
fac[1]=inv[1]=invf[1]=fac[0]=inv[0]=invf[0]=1;
for(int i=2; i<=n; i++) {
fac[i]=fac[i-1]*i%p;
inv[i]=p-(p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
}
Dfs(0,n,n);
printf("%lld\n",ans*invf[n]%p);
return 0;
}
大佬赏瓶冰阔落吧~
0%