题解 P4128 【[SHOI2006] 有色图】

· · 题解

update:修复了几个笔误

置换群论基础练习题。
首先我们发现这个 n \le 53 感觉很不对劲。

最常见的应该就是拆分数了。 那是什么让我们想到置换群论？ ~~题解~~ 本质不同。 写题解的过程中发现变量重名了，所以我们不管题面中的 $m$，设染色数为 $k$。 我们考虑已经将 $n$ 拆成了 $a_1,a_2,a_3,\cdots a_m$ 个数，其中 $a_1\ge a_2 \ge \cdots \ge a_m$，这样方便统计。 求这个的过程可以直接大力 `dfs` 我们知道，一个置换可以表示成若干个循环，这里我们把一个长度为 $n$ 的置换拆成了 $m$ 个循环，循环的长度分别为 $a_1,a_2,a_3,\cdots a_m$。 这样的拆分是无标号的，我们先考虑怎样算出这样的一个拆分序列对应了几个置换。 那么我们先把这么多 $a_i$ ，当做一个个区间，然后往里面填数，填在同一个区间的表示放在同一个置换里，**有顺序影响**。 首先把 $n$ 个数随便排列，这样是 $n!$。 然后考虑每个循环内的起点没有影响，所以要乘上 $\prod_{i=1}^m \dfrac 1{a_i}$。 最后考虑两个大小相同的循环的相对位置没有影响。假设大小为 $l$ 的循环有 $c_l$ 个，那么答案就要乘上 $\prod_l\dfrac 1 {cnt_l!}$。 因此 $num=\dfrac{n!}{\prod a_i \prod_l {cnt_l!}}

这个式子看着很复杂，事实上可以在 dfs 的时候写得好一些，然后在 dfs 过程中就求出来。

然后就可以用 Burnside 引理了。
考虑怎么算 这样一个序列的不动点数量。
考虑一条边，分两种情况讨论。

那么最后答案为

\dfrac{1}{|G|}\cdot\dfrac{n!}{\prod a_i \prod_l {cnt_l!}} k^{\sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)}

我们知道 |G|=n!
所以答案为

\dfrac{k^{\sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)}}{\prod a_i \prod_l {cnt_l}!}

然后就做完了。
在代码中用 dif 表示 \sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)
same 表示 \prod a_i \prod_l {cnt_l!} 的逆元。
cnt 表示上一个数已经重复出现了几遍。
lft 表示在序列中还剩下多少没有被划入置换中。
mx 表示序列的上一个数是什么，同时也是序列的下一个数的最大值限制。

代码：（变量名已经改为和题解相同） 

#include<bits/stdc++.h>
#define rd(x) x=read()
#define ri register int
#define int long long
using namespace std;
int mod=1e9+7;
const int N=100;
inline int read(){int x=0,f=1;char ch=getchar();while((ch>'9' || ch<'0')){if(ch=='-') f=-1;ch=getchar();}while('0'<=ch && ch<='9') x=x*10+(ch^48),ch=getchar();return x*f;}
inline int ksm(int x,int y=mod-2,int z=mod){int ret=1;while (y){if (y&1LL) ret=ret*x%mod;x=x*x%mod;y>>=1LL;}return ret;}
int n,T,k,ans;
int inv[N],fac[N],ifc[N];
void Init(int n){
inv[1]=1;for (ri i=2;i<=n;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
fac[0]=1;for (ri i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
ifc[0]=1;for (ri i=1;i<=n;i++)ifc[i]=ifc[i-1]*inv[i]%mod;}
int a[N],m,dif,same=1;
void dfs(int lft,int mx,int cnt)
{

    if (!lft){ans=(ans+ksm(k,dif)*same)%mod;return;}
    int Dif=dif,Same=same;
    for (int i=1;i<=mx;i++)
    {
        a[++m]=i;
        dif=Dif+i/2;
        for (int j=1;j<m;j++) dif+=__gcd(a[j],i);
        same=Same*inv[i]%mod;
        if (i==a[m-1]) same=same*inv[cnt+1]%mod,dfs(lft-i,min(lft-i,i),cnt+1);
        else dfs(lft-i,min(lft-i,i),1);
        m--;
    }

}
signed main()
{
    rd(n);rd(k);rd(mod);
    Init(n+5);dfs(n,n,0);
    cout<<ans<<endl;
}

在文章最后放两张鏼图
点击链接查看
再放一张