题解 P4128 【[SHOI2006]有色图】
斯德哥尔摩
2018-07-29 13:18:20
[P4128 [SHOI2006]有色图](https://www.luogu.org/problemnew/show/P4128)
这题想起来挺难的。。。
至少我这么认为，直到看了某巨佬的[博客](http://www.cnblogs.com/Konjakmoyu/p/6277483.html)。
首先它是边的置换。
但是我们的$Polya$只能解决点的置换。
所以我们要看一下点置换和边置换之间的关系。
假定一个点置换是$(a_1,a_2,...)(b_1,b_2...)(c_1,c_2...)...$
1. 对于不在一个循环里面的点：
比如$a_1,b_1$, 那么会有边循环$((a1,b1),(a2,b2)...)$
设$a_i$循环的循环节是$l_1$，$b_i$循环的循环节是$l_2$,那么形成的边循环的循环节显然是$lcm(l_1,l_2)$。
一共有$l_1* l_2$个点对，每个点对都在一个循环节为$lcm(l_1,l_2)$的循环上，所以一共有$\frac{l_1* l_2}{lcm(l_1,l_2)}=gcd(l_1,l_2)$个循环节，所以$C(f)=m^{gcd(l_1,l_2)}$。
（回到$Burnside$引理，$C$为置换之后仍为自身的数目，就是说要循环节里的每条边都一样的颜色）
2. 对于在一个循环里面的点：
比如$a_1,a_2$。
设$a_i$的循环节为$l_1$。
如果$l_1$是奇数，那么循环长度为$l_1$，一共有$\left(\begin{array}{c}l_1\\2\end{array}\right)$个点对，所以是$\frac{l_1-1}{2}$个循环节，所以$C(f)=m^{\frac{l_1-1}{2}}$。
如果$l_1$是偶数，除了上面这种情况之外，还有一种的循环节是$\frac{l_1}{2}$（就是两个点刚好相隔半个周期，而边是双向的），所以一共有$\frac{\left(\begin{array}{c}l_1\\2\end{array}\right)-\frac{l_1}{2}}{l1}+1=\frac{l_1}{2}$个点对。
综上，边的置换的循环数为：
$$\sum_{i=1}^{k}\lfloor \frac{l_i}{2}\rfloor+\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}gcd(l_i,l_j)$$
实际$N!$个点的置换中，有多少$l_1<l_2<...<l_i$呢？
若将一个循环看成一个圆形的排列，现在要把$N$个人分配到$k$个长度分别为$l_1,l_2,l_3,...,l_k$的独立不相关圆排列中，并且$l_1<=l_2<=l_3<=...<=l_k$。
因为存在$l_i==l_{i+1}$的情况，设$B_i$为有多少$l_j$满足$l_j==i$。
则总分配数为：
$$S=\frac{N!}{\prod_{i=1}^{k}l_i* \prod_{i=1}^{k}B_i!}$$
然后我们通过搜索，确定点的置换长度$l_1<=l_2<=l_3<=...<=l_k$，满足该特征的个数为$S$，而该特征的点置换引导出的边置换循环数为$C$。
于是我们所求的答案就解决了：$$Ans=Ans+S* m^C$$
所以代码很简单，只要枚举$N$的拆分，然后计算不动点就好了。
但是又有除，又有模，怎么办？
套路求逆元，注意到$p\in prime$，直接费马小定理即可，不用扩欧了。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 70
using namespace std;
long long n,m,p,ans=0,fact[MAXN],num[MAXN];//直接开long long
inline long long read(){//快读
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long gcd(long long x,long long y){//这个gcd应该都会吧
if(!y)return x;
return gcd(y,x%y);
}
long long mexp(long long a,long long b,long long c){//快速幂也应该会吧
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
void get_answer(int x){//累计答案
int top=1;
long long sum=0,mul=1;
for(int i=1;i<=x;i++)sum+=num[i]/2;
for(int i=1;i<=x;i++)
for(int j=i+1;j<=x;j++)
sum+=gcd(num[i],num[j]);
for(int i=1;i<=x;i++)mul=(mul*num[i])%p;
for(int i=2;i<=x;i++){
if(num[i]!=num[i-1]){
mul=(mul*fact[top])%p;
top=0;
}
top++;
}
mul=(mul*fact[top])%p;
mul=fact[n]*mexp(mul,p-2,p)%p;
ans=(ans+mul*mexp(m,sum,p)%p)%p;//记得每次都要累计
}
void dfs(int x,int h,int s){//直接暴搜
if(!h)get_answer(x-1);
if(h<s)return;
for(int i=s;i<=h;i++){
num[x]=i;
dfs(x+1,h-i,i);
num[x]=0;
}
}
void work(){
dfs(1,n,1);
ans=ans*mexp(fact[n],p-2,p)%p;
printf("%lld\n",ans);
}
void init(){//读入+预处理阶乘
n=read();m=read();p=read();
fact[0]=1;
for(int i=1;i<=n;i++)fact[i]=(fact[i-1]*i)%p;
}
int main(){//主函数So easy!
init();
work();
return 0;
}
```