Chlience

【题解】POJ 2888 Magic Bracelet
Problem一个长度为 $n$ 的环,用 $m$ 种颜色染色,有 $k$ 对颜色不能同时出现,问本质不同的方案数...
扫描右侧二维码阅读全文
14
2019/01

【题解】POJ 2888 Magic Bracelet

Problem

一个长度为 $n$ 的环,用 $m$ 种颜色染色,有 $k$ 对颜色不能同时出现,问本质不同的方案数

Thought

先不考虑本质不同的方案
先考虑如何计算出所有的方案

显然,我们可以维护一个矩阵来转移,然后求出最后一个矩阵后再 $m^2$ 判断一下即可

显然,如果一个当前合法的方案旋转后必然合法,考虑直接上 $Polya$

$$ L=\frac{1}{|G|}\sum_{i=1}^{s}m^{c(g_i)} $$

但是貌似是不能直接套的吧...

因为对于某个旋转而言其 $m​$ 并不能做到任选,还是会导致冲突的发生
既然如此,不同的几个循环必然大小相等,元素相邻,我们能不能直接对这几个循环搞事情呢?

相当于 $Burnside 计数时取 $f(gcd(i,n))$ 替代 $D(g_i)$
可用类似于 $Polya$ 的证明方式思考

同样枚举 $gcd$,变形,发现只会有 $\sqrt n$ 个取值,美滋滋!

$$ L=\frac{1}{|G|}\sum_{d|n}\sum_{i=1}^{n}[gcd(i,n)=d]f(d)\\ L=\frac{1}{|G|}\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]f(d)\\ L=\frac{1}{|G|}\sum_{d|n}f(d)*\phi(\frac{n}{d}) $$

$f(x)$ 可以用矩阵乘法在 $m^3\log n$ 的时间内求出

总复杂度 $O(\sqrt n m^3\log n+n^{\frac{3}{4}})$

Code

#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100000;
const int mod = 9973;
int pri[N] , pri_num;
bool np[N];
int n , m;
struct Matrix {
    int a[10][10];
    void clear() {memset(a , 0 , sizeof(a));}
    int* operator [] (const int x) {return a[x];}
}I;
Matrix operator * (Matrix a , Matrix b) {
    Matrix ans; ans.clear();
    for(int i = 0 ; i < m ; ++ i)
        for(int j = 0 ; j < m ; ++ j)
            for(int k = 0 ; k < m ; ++ k) {
                ans[i][j] += a[i][k] * b[k][j] % mod;
                if(ans[i][j] >= mod) ans[i][j] -= mod;
            }
    return ans;
}
Matrix qpow(Matrix a , int b) {
    Matrix ans; ans.clear();
    for(int i = 0 ; i < m ; ++ i) ans[i][i] = 1;
    while(b) {
        if(b & 1) ans = a * ans;
        a = a * a;
        b >>= 1;
    }
    return 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 qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = a * ans % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void getPri() {
    for(int i = 2 ; i < N ; ++ i) {
        if(!np[i])
            pri[++ pri_num] = i;
        for(int j = 1 ; j <= pri_num && i * pri[j] < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
int getPhi(int x) {
    int ans = x;
    for(int i = 1 ; i <= pri_num && pri[i] <= x ; ++ i)
        if(x % pri[i] == 0) {
            ans /= pri[i];
            ans *= (pri[i] - 1);
            while(x % pri[i] == 0) x /= pri[i];
        }
    if(x != 1) {
        ans /= x;
        ans *= (x - 1);
    }
    return ans % mod;
}
int f(int x) {
    Matrix ans = qpow(I , x);
    int sum = 0;
    for(int i = 0 ; i < m ; ++ i) {
        sum += ans[i][i];
        if(sum >= mod) sum -= mod;
    }
    return sum;
}
void work() {
    n = read(); m = read();
    for(int i = 0 ; i < m ; ++ i)
        for(int j = 0 ; j < m ; ++ j)
            I[i][j] = 1;
    int k = read();
    while(k --) {
        int a = read() - 1 , b = read() - 1;
        I[a][b] = I[b][a] = 0;
    }
    int ans = 0;
    for(int i = 1 ; i * i <= n ; ++ i) {
        if(n % i == 0) {
            ans += f(i) * getPhi(n / i) % mod;
            if(ans >= mod) ans -= mod;
            if(i * i != n) {
                ans += f(n / i) * getPhi(i) % mod;
                if(ans >= mod) ans -= mod;
            }
        }
    }
    printf("%d\n" , ans * qpow(n % mod , mod - 2) % mod);
}
int main() {
    getPri();
    int t = read();
    while(t -- ) work();
    return 0;
}
Last modification:January 16th, 2019 at 09:28 am

Leave a Comment