Chlience

【题解】BZOJ 1478 Sgu282 Isomorphism
Problem给定 $n$ 个节点的无向完全图,用 $m$ 种颜色对边进行染色求有多少种本质不同的染色方法两种染色...
扫描右侧二维码阅读全文
14
2019/01

【题解】BZOJ 1478 Sgu282 Isomorphism

Problem

给定 $n$ 个节点的无向完全图,用 $m$ 种颜色对边进行染色
求有多少种本质不同的染色方法
两种染色方法本质不同当且仅当无法通过节点重新编号使两者相同

Thought

首先,这是由点的置换导致的边的置换
所以考虑枚举每个点置换对边置换的影响

对于某个点置换 $(a_1,a_2,\cdots)(b_1,b_2,\cdots)(c_1,c_2,\cdots)$

先计算某条边的端点在一个循环中的情况

设循环 $a$ 的大小为 $A$

考虑任意一条边 $(a_i,a_j)$ 在置换之后的循环长度
相当于在同一个环内两个点同时进行旋转,问要多少次旋转才能使得两者回到开始的位置

在$A$ 为奇数时,答案为 $A$
那么在 $a$ 中则会有 $\frac{A(A-1)}{2A}=\frac{A-1}{2}$ 个这样的循环,循环长度为 $A$

在 $A$ 为偶数时,对于不相对的两个点,答案为 $A$,对于相对的两个点,答案为 $\frac{A}{2}$
那么一共有 $A/2$ 对相对点,他们同属于一个循环,循环长度为 $\frac{A}{2}$
一共有 $\frac{(A-1)(A-1)}{2}$ 对不相对点,会有 $\frac{A-2}{2}$ 个循环,循环长度为 $A$
总循环数为 $\frac{A}{2}$

那么对于边端点在同一个循环内的情况,一共贡献答案 $\left \lfloor\frac{A}{2}\right \rfloor$

再考虑某条边的端点不在一个循环的情况

设循环 $a$ 的大小为 $A$,循环 $b$ 的大小为 $B$

显然其端点在 $a,b$ 中的边仍然在 $a,b$ 中
考虑任意一条边 $(a_i,b_j)$ 在置换后的循环长度
相当于在两个环内两个点同时进行旋转,问要多少次旋转才能使得两者回到开始的位置

显然这样的答案为 $LCM(A,B)$
那么在 $a,b$ 中则会有 $\frac{AB}{LCM(A,B)}$ 即 $gcd(A,B)$ 个这样的循环,循环长度为 $LCM(A,B)$

那么对于边端点不在同一个循环内的情况,一共贡献答案 $gcd(A,B)$

所以,点置换引起的边置换的循环数就能够计算出来了
我们设 $L_i$ 为第 $i$ 个点循环大小,则边置换的循环数 $C$ 为:

$$ C=\sum_{i=1}^{s}\left \lfloor\frac{L_i}{2}\right \rfloor+\sum_{i=1}^{s-1}\sum_{j=i+1}^{s}gcd(L_i,L_j) $$

不妨设 $L_1\leq L_2\leq\cdots\leq L_s$,对于满足这样结构的点置换可以一起算出答案

有多少个这样的点置换呢?
答案是:

$$ S=\frac{n!}{\prod_{i=1}^s(L_i!)\prod_{i=1}^n(S_i!)} $$

其中 $S_i$ 表示长度为 $i$ 的循环个数

考虑将一个 $n$ 的排列打乱,一共有 $n!$ 种情况,前 $L_1$ 个作为第一个循环,接下来 $L_2$ 个作为第二个循环...
由于每个循环内的节点进行旋转是不影响答案的,所以需要除去每个循环的长度
同时,因为存在 $L_i=L_{i+1}$ 的情况,对于相同长度的循环,其排列顺序也不影响答案,所以需要除去长度相等循环不同排列的贡献

那么,只需要枚举 $L_1,L_2,...$ ,就可以算出答案了:

$$ L=\frac{1}{n!}\sum_{i} S_i*m^{C_i} $$

由于 $gcd$ 属于复杂度瓶颈,建议将其预处理以优化速度

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 64;
int pro[N] , inv[N] , pro_inv[N] , _gcd[N][N];
int L[N] , tot;
int n , m , p , ans;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int gcd(int a , int b) {
    if(a < b) swap(a , b);
    return b ? gcd(b , a % b) : a;
}
void getInv() {
    pro[1] = inv[1] = pro_inv[1] = 1;
    for(int i = 2 ; i <= n ; ++ i) {
        pro[i] = 1ll * pro[i - 1] * i % p;
        inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
        pro_inv[i] = 1ll * pro_inv[i - 1] * inv[i] % p;
    }
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= n ; ++ j)
            _gcd[i][j] = gcd(i , j);
}
int qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}
int addAns() {
    int C = 0 , S = pro[n] , sum = 1;
    for(int i = 1 ; i <= tot ; ++ i) {
        C += L[i] / 2;
        for(int j = i + 1 ; j <= tot ; ++ j)
            C += _gcd[L[i]][L[j]];
        
        S = 1ll * S * inv[L[i]] % p;
        if(L[i] == L[i - 1]) ++ sum;
        else {
            S = 1ll * S * pro_inv[sum] % p;
            sum = 1;
        }
    }
    S = 1ll * S * pro_inv[sum] % p;
    return 1ll * S * qpow(m , C) % p;
}
void dfs(int x , int len) {
    if(x == n) {
        ans += addAns();
        if(ans >= p) ans -= p;
    }
    else {
        for(int i = len ; i <= n - x ; ++ i) {
            L[++ tot] = i;
            dfs(x + i , i);
            L[tot --] = 0;
        }    
    }
}
int main() {
    n = read(); m = read(); p = read();
    getInv();
    dfs(0 , 1);
    ans = 1ll * ans * pro_inv[n] % p;
    printf("%d\n" , ans);
    return 0;
}
Last modification:January 16th, 2019 at 09:25 am

Leave a Comment