NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  • 题解
  • Description

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

    Input

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

    Output

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

    Sample Input

    1
    3 4 97

    Sample Output

    1
    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$$

    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #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);
    }

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

    本文最后更新于 天前,文中所描述的信息可能已发生改变