BZOJ1478/1815 Sgu282 Isomorphism/[Shoi2006]color 有色图

Author Avatar
WildRage 3月 06, 2018
  • 在其它设备中阅读本文章

Description

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

Input

仅一行包含三个数,$N$、$M$、$P$。

Output

仅一行,为染色方法数 $mod P$ 的结果。

Sample Input

3 4 97

Sample Output

20

题解

假定一个点置换,把它表示为循环,比如是$(a_1,a_2,….)(b_1,b_2…)(c_1,c_2…)…$

  1. 对于不在一个循环里面的点: 比如$a1,b1$, 那么会有边循环$((a1,b1),(a2,b2)…)$设$a$循环的循环节是$l1,b$循环的循环节是$l2$,那么形成的边循环的循环节显然是$LCM(l1,l2)$。一共有$l1*l2$个点对,每个点对都在一个循环节为$LCM(l1,l2)$的循环上,所以一共有$l1*l2/LCM(l1,l2)=GCD(l1,l2)$个循环节,所以$C(f)=m^GCD(l1,l2)$。(回到$Burnside$引理,$C$为置换之后仍为本身的数目,就是说要循环节里的每条边都一样的颜色)
  2. 对于在一个循环里面的点: 比如$a1$、$a2$。设这个$a$循环的循环节为$l1$。
    • 如果$l1$是奇数,那么循环长度为$l1$,一共有$C(l1,2)$个点对,所以是$(l1-1)/2$个循环节,所以$C(f)=m^((l1-1)/2)$。
    • 如果$l1$是偶数,除了上面这种情况之外,还有一种的循环节是$l1/2$(就是两个点刚好相隔半个周期,而边是双向的),所以一共有$(C(l1,2)-l1/2)/l1+1=l1/2$个点对。

整理一下:

$$C = \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)} }$$

$$S = \frac{ N! }{\prod_{i = 1} ^ {k} \times \prod_{i = 1}^{k}{ B_i! } }$$

$$Ans = Ans + S \times m^C$$

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


知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接:https://blog.wildrage.xyz/2018/03/06/135/