题解 P4128 【[SHOI2006]有色图】

· · 题解

P4128 [SHOI2006]有色图

这题想起来挺难的。。。

至少我这么认为，直到看了某巨佬的博客。

首先它是边的置换。

但是我们的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，直接费马小定理即可，不用扩欧了。

附代码：

#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;
}