POJ2888 Magic Bracelet [矩阵快速幂+Burnside+欧拉函数]

$MagicBracelet$Magic Bracelet

$Description$Description
给一条长度为 $n$n的项链，有 $m$m种颜色，另有 $k$k条限制，每条限制为不允许 $x,y$x,y颜色连在一起。
求有多少种本质不同的染色方式，本质不同的两种染色方式旋转不能互相得到 .

$正解部分$正解部分
对于 置换: “旋转 $k$k 个单位”
在没有颜色限制的情况下, 染色方案数为 $M^{gcd(N,k)}$Mgcd(N,k),

在有颜色限制的情况下,
$不同循环节的元素相互之间是挨着的,$不同循环节的元素相互之间是挨着的,

• 要保证第 $i$i 个与第 $i+1,i-1$i+1,i−1个循环节颜色不同 .
• 由于是环, 还需保证第 $1$1个与第 $N$N个循环节颜色不同 .

在以上限制下, 如何求解方案数呢?
设 $F[i,j]$F[i,j] 表示前 $i$i 个元素, 第 $i$i 个元素颜色为 $j$j 的方案数, $ld[i,j]=1/0$ld[i,j]=1/0 表示 $i$i 和 $j$j 是否可以放到一起.
考虑到首尾相连, 枚举第 $1$1个循环节选的 $col$col 颜色, 进行 $dp$dp,

$\{\begin{array}{c}F[1,col]=1,\\ \\ F[i,j]={\sum }_{k=1}^{M}ld[j,k]\ast F[i-1,k]i\in [2,gcd(N,k\left)\right),\\ \\ F\left[gcd\right(N,k),j]={\sum }_{k=1,k!=col}^{M}ld[j,k]\ast F\left[gcd\right(N,k)-1,k]\end{array}$⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​F[1,col]=1, F[i,j]=∑k=1M​ld[j,k]∗F[i−1,k]         i∈[ 2,gcd(N,k) ), F[gcd(N,k),j]=∑k=1,k != colM​ld[j,k]∗F[gcd(N,k)−1,k]​

于是 ${\sum }_{i=1}^{M}F\left[gcd\right(N,k),i]$∑i=1M​F[gcd(N,k),i] 即为该置换方案数 , 暂存到 $F\left[gcd\right(N,k),0]$F[gcd(N,k),0] 里.

$中间的式子可以使用矩阵快速幂优化$中间的式子可以使用矩阵快速幂优化

再看我们要求的式子
$L=\frac{1}{N}\sum _{i=1}^{N}F\left[gcd\right(N,k),0]$L=N1​i=1∑N​F[gcd(N,k),0]
变为
$L=\frac{1}{N}\sum _{d\mid N}F[d,0]\ast \phi \left(\frac{N}{d}\right)$L=N1​d∣N∑​F[d,0]∗φ(dN​)

至于为什么请点击这里看拓展2

时间复杂度 $O(M^4\ast \sqrt{N}\ast logN)$O(M4∗N ​∗logN).

如果你耐心的看到了这里, 那么不幸的告诉你, 这个方法会 TLE

建立一个 $M\ast M$M∗M 的矩阵, $C_{i,j}=1$Ci,j​=1 表示 $i$i 可以走到 $j$j,
计算出这个矩阵 $\frac{N}{gcd(N,k)}$gcd(N,k)N​ 次方, 则对角线的值加起来即为该置换的方案总数 .

注意 求解 $phi$phi的时候不能 模.

调了一个晚上, 竟然是 $phi$phi忘记加特判了!!

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#define reg register

const int mod = 9973;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int N;
int M;
int K;

struct Matrix{ int C[12][12]; Matrix(){ memset(C, 0, sizeof C); } } A;

Matrix Modify(Matrix a, Matrix b){ // 
        Matrix s;
        for(reg int i = 1; i <= M; i ++)
                for(reg int j = 1; j <= M; j ++){ 
                        int &t = s.C[i][j];
                        for(reg int k = 1; k <= M; k ++)
                                t = (t+a.C[i][k]*b.C[k][j]) % mod;
                }
        return s;
}

Matrix KSM(Matrix a, int b){ //
        Matrix s;
        for(reg int i = 1; i <= M; i ++) s.C[i][i] = 1;
        while(b){
                if(b & 1) s = Modify(s, a);
                a = Modify(a, a);
                b >>= 1;
        }
        return s;
}

int phi(int x){ //
        int s = x;
        for(reg int i = 2; i*i <= x; i ++){
                if(x % i) continue ;
                s = s/i*(i-1);
                while(x%i == 0) x /= i;
        }
        if(x > 1) s = s/x*(x-1);
        return s%mod;
}

int KSM_2(int a, int b){ //
        int s = 1;
        a %= mod;
        while(b){
                if(b & 1) s = (s*a) % mod;
                a = (a*a) % mod;
                b >>= 1;
        }
        return s;
}

int gcd(int a, int b){ return !b?a:gcd(b, a%b); } //

int Calc(int k){
        int tmp = 0;
        Matrix B = KSM(A, k);
        for(reg int i = 1; i <= M; i ++) tmp += B.C[i][i], tmp %= mod; 
        tmp = (phi(N/k)*tmp) % mod;
        return tmp;
}

void Work(){
        N = read(), M = read(), K = read();
        for(reg int i = 1; i <= M; i ++)
                for(reg int j = 1; j <= M; j ++) A.C[i][j] = 1;
        for(reg int i = 1; i <= K; i ++){
                int a = read(), b = read();
                A.C[a][b] = A.C[b][a] = 0;
        }
        int Ans = 0;
        for(reg int k = 1; k*k <= N; k ++)
                if(N % k == 0){
                        Ans = (Ans + Calc(k)) % mod; 
                        int k2 = N/k;
                        if(k != k2) Ans = (Ans + Calc(k2)) % mod;
                }
        Ans = 1ll*Ans * KSM_2(N, mod-2) % mod;
        printf("%d\n", Ans);
}

int main(){
        int T = read();
        while(T --) Work();
        return 0;
}