我花了三個小時寫了一道題的六千字題解....（POJ 2888 Magic Bracelet）-有解無憂

整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

~~一道簡單的題目~~
在這里插入圖片描述

Problem 24.2.1 POJ 2888 Magic Bracelet / AcWing 3134. 魔法手鏈（（Burnside引理，矩陣快速冪優化DP，歐拉函式））

給定 m m m 種不同顏色的魔法珠子，每種顏色的珠子的個數都足夠多，

現在要從中挑選 n n n 個珠子，串成一個環形魔法手鏈，

魔法珠子之間存在 k k k 對排斥關系，互相排斥的兩種顏色的珠子不能相鄰，否則會發生爆炸，（同一種顏色的珠子之間也可能存在排斥）

請問一共可以制作出多少種不同的手鏈，

注意，如果兩個手鏈經旋轉后能夠完全重合在一起，對應位置的珠子顏色完全相同，則視為同一種手鏈，

答案對 9973 9973 9973 取模，
1 ≤ T ≤ 10 1≤T≤10 1≤T≤10
1 ≤ n ≤ 1 0 9 1≤n≤10^9 1≤n≤109
gcd ? ( n , 9973 ) = 1 \gcd(n,9973)=1 gcd(n,9973)=1
1 ≤ m ≤ 10 1≤m≤10 1≤m≤10
0 ≤ k ≤ m ( m + 1 ) 2 0≤k≤\frac{m(m+1)}{2} 0≤k≤2m(m+1)?
1 ≤ a , b ≤ m 1≤a,b≤m 1≤a,b≤m

Solution

這里因為多了很多互斥關系，也就是不同的回圈之間有一定有了很多限制，所以不能使用 Polya 定理，只能使用 Burnside引理，

本題比上一題簡化了，只有回圈這一種置換，我們可以發現 n n n 很大，需要模 9973 9973 9973 ，并且保證 gcd ? ( n , 9973 ) = 1 \gcd(n,9973)=1 gcd(n,9973)=1 也就意味著我們最后除以 n n n 的時候可以直接使用乘法逆元，

我們設旋轉的距離為 k = 0 , 1 , 2 , ? n ? 1 k=0,1,2,\cdots n-1 k=0,1,2,?n?1，

由于需要使用 Burnside引理，所以我們需要求一下不動點的數量，

設一個點初始位置為 x x x ，那么每轉一次就會轉到 x + k x+k x+k 的位置

如圖 24.2.1 所示

圖 24.2.1

那么轉多少會重復呢（回到起點，出現回圈）

回到起點不一定只賺一圈，可能需要轉很多圈，由于點數是有限的，所以我們這樣每次走 k k k 步是一定會重復的，

這里很明顯可以得到一個同余方程：

x + k t ≡ x ( m o d ?? n ) x+kt\equiv x(\mod n) x+kt≡x(modn)

k t ≡ 0 ( m o d ?? n ) kt\equiv 0(\mod n) kt≡0(modn)

即

k t = n r + c kt=nr+c kt=nr+c
t = n d t=\cfrac{n}{d} t=dn?

其中 d = gcd ? ( n , k ) d =\gcd(n,k) d=gcd(n,k)

這也就意味著我們走 n d \cfrac{n}{d} dn? 步就會出現回圈

即：每一個回圈一共有 n d \cfrac{n}{d} dn? 個點，

即：每個回圈均使用了 n d \cfrac{n}{d} dn? 個點，而我們一共有 n n n 個點，

所以一共會有 n n d = d \cfrac{n}{\frac{n}{d}}=d dn?n?=d 個回圈，

即我們僅有旋轉這一種置換操作，會得到 d = gcd ? ( n , k ) d=\gcd(n,k) d=gcd(n,k) 個回圈，

我們發現每個回圈均有 n d \cfrac{n}{d} dn? 個點，我們可以先分析一個回圈，其余的回圈與該回圈性質相同，分析一個回圈即可得到所有的回圈的答案，

我們發現了這一個回圈的 n d \cfrac{n}{d} dn? 個點的一個性質：我們按照原本的點的編號的順序看，任意兩個相鄰的點之間的距離均為 d d d ，

證明： d = gcd ? ( n , k ) d=\gcd(n,k) d=gcd(n,k)

設 k ′ = k d k'=\cfrac{k}{d} k′=dk?， n ′ = n d n'=\cfrac{n}{d} n′=dn?，

由于我們每次走都是跳 k k k 步，然后如果跳過了一圈長度為 n n n 以后，就 % n \% n %n，因為 k k k 和 n n n 是 d d d 的倍數，所以我們從起點 x x x 出發，每次走到的點到起點的距離都必然是 d d d 的倍數，然后因為我們一共走了 n d \cfrac{n}{d} dn? 步，而每一步又都是 d d d 的倍數，也就是說我們每次走的就是距離可以寫成表格，并且我們將 0 , d , 2 d ? 0,d,2d\cdots 0,d,2d? 做一個映射:

距離   0  d  2d  3d  ...  (n / d - 1) * d = n - 1  
步數   0  1  2   3   ...           n / d           
映射   0  1  2   3   ...           n / d

也就意味著我們每一步走的距離均為 d d d ，

綜上所訴，該性質得證 □

這個性質也就意味著對于每一個回圈（我們當前分析的就是一個回圈），我們只需要考慮 d d d 的倍數的這 n d \cfrac{n}{d} dn? 個點即可，

所以我們僅考慮這些點的映射（ 0 , 1 , 2 , 3 , ? 0,1,2,3,\cdots 0,1,2,3,?），就會得到一個長度為 n ′ = n d n'=\cfrac{n}{d} n′=dn? 的一個小環（共有 n ′ = n d n'=\cfrac{n}{d} n′=dn? 個點），并且每次跳的距離是 k ′ k' k′，其中 k ′ = k d k'=\cfrac{k}{d} k′=dk?，即 k ′ k' k′ 與 n n n 互質，也就可以證明這樣跳，一定能遍歷到這個小環的所有的點，

小環如圖 24.2.2 所示

圖 24.2.2

因為可以遍歷這個小環的所有的點，可以得到：

k ′ × 0 , k ′ × 1 , k ′ × 2 , ? ? , k ′ × ( n ? 1 ) k'\times 0,k'\times 1,k'\times 2,\cdots,k'\times (n-1) k′×0,k′×1,k′×2,?,k′×(n?1) 構成了一個 0 0 0 ~ n n n 的一個簡化剩余系，（即該 k ′ k' k′ 的序列在 m o d ?? n \mod n modn 意義下還是 0 0 0 ~ n ? 1 n-1 n?1）

證明：

我們使用反證法，

假設 k ′ × 0 , k ′ × 1 , k ′ × 2 , ? ? , k ′ × ( n ? 1 ) k'\times 0,k'\times 1,k'\times 2,\cdots,k'\times (n-1) k′×0,k′×1,k′×2,?,k′×(n?1) 不是 0 0 0 ~ n n n 簡化剩余系，即序列中存在兩個下標， i ≠ j i≠j i?=j 且 k ′ i = k ′ j k'i=k'j k′i=k′j

k ′ i = k ′ j k'i=k'j k′i=k′j

實際上就是：

k ′ ( i ? j ) ≡ 0 ( m o d ?? n ) k'(i-j)\equiv0(\mod n) k′(i?j)≡0(modn)

因為 k ′ k' k′ 與 n n n 互質，所以可以吧 k ′ k' k′ 去掉

即： i ≡ j ( m o d ?? n ) i\equiv j(\mod n) i≡j(modn)

而 0 ≤ i , j < n 0\le i,j< n 0≤i,j<n，

若 i ≡ j ( m o d ?? n ) i\equiv j(\mod n) i≡j(modn)，則定有 i = j i=j i=j，與前提不符，產生矛盾，

故對于所有的 k ′ i k'i k′i， k ′ j k'j k′j ， 0 ≤ i , j < n 0\le i,j <n 0≤i,j<n，任意兩個數均不相同，故在 % n \%n %n 的意義下一定能遍歷完 0 0 0 ~ n ? 1 n-1 n?1 里的每一個數，故一定是 0 0 0 ~ n ? 1 n-1 n?1 的一個簡化剩余系，

綜上所訴，該性質得證 □

由于我們剛剛得到的這一個回圈的 n d \cfrac{n}{d} dn? 個點的一個性質：我們按照原本的點的編號的順序看，任意兩個相鄰的點之間的距離均為 d d d ，

以及另一個性質 k ′ × 0 , k ′ × 1 , k ′ × 2 , ? ? , k ′ × ( n ? 1 ) k'\times 0,k'\times 1,k'\times 2,\cdots,k'\times (n-1) k′×0,k′×1,k′×2,?,k′×(n?1) 構成了一個 0 0 0 ~ n n n 的一個簡化剩余系，也就意味著在 % n \%n %n 的意義下一定能遍歷完 0 0 0 ~ n ? 1 n-1 n?1 里的每一個數

而我們僅考慮這些點的映射（ 0 , 1 , 2 , 3 , ? 0,1,2,3,\cdots 0,1,2,3,?），就會得到一個長度為 n ′ = n d n'=\cfrac{n}{d} n′=dn? 的一個小環（共有 n ′ = n d n'=\cfrac{n}{d} n′=dn? 個點），并且每次跳的距離是 k ′ k' k′，我們再回代，即乘上一個 d d d 以后，就意味著可以遍歷所有與 x x x 的距離為 d d d 的倍數的點，

而最開始我們由得到了僅考慮旋轉這一種置換，我們一共會有 d d d 個回圈，每次回圈的步數（走的距離）均為 d d d ，也就是每個回圈的起點，為 x , x + d , x + 2 d , ? x,x+d,x+2d,\cdots x,x+d,x+2d,?，

也就意味著第一個回圈的區間為 [ x , x + d ? 1 ] [x,x+d-1] [x,x+d?1]，第二個回圈的區間為 [ x + d , x + 2 d ? 1 ] [x+d,x+2d-1] [x+d,x+2d?1]，以此類推，我們之前說過，由于僅是旋轉操作，得到的 d d d 個回圈的解法一摸一樣，每一個回圈的不動點的個數均相同，即為每一個回圈內部的點的顏色按照順序相同，

例如：第一個回圈的顏色為 1 2 3 4 5 ，則第二個回圈的顏色同樣為 1 2 3 4 5 ，以此類推，

具體圖形如圖 24.2.3 所示：

圖 24.2.3

因為每一個回圈區間內部點的顏色都是相同的，也就意味著每個區間的最后一個點和下一個區間的第一個點相鄰，而下一個區間的第一個點和這個區間的第一個點的顏色是相同的，所以我們就可以看作每個區間的最后一個點和該區間的第一個點是相鄰的，也就意味著每個長度為 d d d 的小區間又可以看作是一個回圈，也就可以畫成一個更小的圈，

也就意味著我們只需要討論一下這個長度為 d d d 的圈有多少個染色方案就行啦！

這個染色方案的數量就是這個置換的這個回圈的不動點的數量，（因為這個圈固定以后，這一個段就固定了，那么這一小段的這個區間固定了以后，因為整個環分為 d d d 段，也就是 d d d 個回圈，那么整個環也就固定了）

也就是說我們只需要求一下長度為 d d d 的，滿足要求的這個環的染色方案即可，

那么怎么求解這個方案數呢？我們僅需列舉一下這個環的起點

在這里插入圖片描述
我們分情況討論一下，我們列舉一下 d d d這個點是那種顏色，因為一共有 m m m 種顏色，所以我們 1 1 1 ~ m m m 列舉一遍，

我們求一下 d d d 染乘 1 1 1 的所有方案， d d d 染 2 2 2 的所有方案， ? \cdots ? 到 d d d 染 m m m 的所有方案，

若 d d d 染的顏色為 i i i ，我們可以使用 DP 來求解這個答案，

f [ i ] [ j ] f[i][j] f[i][j] 表示的是染完了前 i i i 個珠子的顏色，并且最后一個珠子的顏色為 j j j 的所有方案的數量，

例如我們將 d d d 染為 i i i，即 f[0][i] = 1，其余均為 0 0 0：f[0][1] = f[0][2] = ...f[0][m] = 0;，（ d d d 就是 1 1 1 前面的這個珠子，編號為 0 0 0）

暴力轉移即可：

f[i][j] += vis[k][j] ? f[i - 1][k] : 0;

其中 vis[k][j] 表示 k k k 和 j j j 是否互斥（由題目輸入），如果不互斥的話說明 k k k 和 j j j 可以相鄰，

最后的答案：分類討論：

若 d d d 染色為 1 1 1 ，答案為 f[d][1]，其余同理，

但是由于本題的 n ≤ 1 0 9 n\le 10^9 n≤109 ，暴力轉移無法通過，所以我們可以使用矩陣乘法來優化，

設 F [ i ] = f [ i ] [ 1... m ] F[i]=f[i][1...m] F[i]=f[i][1...m]

則 F [ i ] = F [ i ? 1 ] ? M F[i] = F[i - 1] * M F[i]=F[i?1]?M

其中轉移矩陣 M 就代表若 k k k 和 j j j 可以相鄰，互不排斥，就為 1 1 1 ，否則就為 0 0 0 ，（該矩陣的轉移方程實際上展開以后就是上面的DP轉移方程）

則答案 F [ d ] = F [ 0 ] ? M d F[d]=F[0]*M^d F[d]=F[0]?Md，我們可以來使用快速冪優化，

總時間復雜度為 O ( M 3 l o g n ) O(M^3logn) O(M3logn)

最后一個問題，因為 n n n 很大，所以我們列舉 k k k 的時候不可能直接列舉，

我們發現 k k k 的唯一作用就是得到 d = gcd ? ( n , k ) d=\gcd(n,k) d=gcd(n,k)，而我們非常容易就可以發現很多 g c d ( n , k ) gcd(n,k) gcd(n,k) 是相同的，因此我們就可以將 k k k 按照所有的最大公約數分類，也就是直接列舉 gcd ? ( n , k ) \gcd(n,k) gcd(n,k) 即可，也即是說我們只需要列舉 n n n 的約數即可，那么就意味著最多只會有 φ ( n ≤ 1 0 9 ) ≤ 1600 \varphi(n\le10^9)\le 1600 φ(n≤109)≤1600 種，

則對于所有的 d = gcd ? ( n , k ) d=\gcd(n,k) d=gcd(n,k) 都可以直接使用快速冪來求解，分類之后我們肯定要算一下每一個 d d d 都包含了多少個 k k k，換句話說就是一共有多少個 k k k 滿足 gcd ? ( n , k ) = d \gcd(n,k)=d gcd(n,k)=d 呢？

我們發現這就是一個非常經典的歐拉函式問題，

gcd ? ( n , k ) = d \gcd(n,k)=d gcd(n,k)=d

即： gcd ? ( n d , k d ) = 1 \gcd(\frac{n}{d},\frac{k}{d})=1 gcd(dn?,dk?)=1 的個數，也就是在 0 0 0 ~ n d \cfrac{n}{d} dn? 種互質的個數，也就是 φ ( n d ) \varphi(\cfrac{n}{d}) φ(dn?)，直接暴力求，復雜度 O ( φ ( n d ) O(\sqrt{\varphi(\cfrac{n}{d}}) O(φ(dn? ?)，

這里的答案（所有不動點的和）就是 a n s = ∑ d = 0 n F [ 0 ] ? M d ? φ ( n d ) ans=\sum_{d=0}^{n}F[0]*M^d*\varphi(\cfrac{n}{d}) ans=d=0∑n?F[0]?Md?φ(dn?)

最后的答案就是所有不動點的平均值即不動點個數和除以所有置換的個數，

因為我們這里的置換是旋轉，一共有 n n n 個點，所以一共有 n n n 種置換

即最后的答案為： a n s n \cfrac{ans}{n} nans?，也就是乘上 n n n 模 9973 9973 9973 的逆元 a n s × i n v ( n ) ans\times inv(n) ans×inv(n)

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 11, P = 9973;

int m;
struct Matrix
{
    int a[N][N];
    Matrix()
    {
        memset(a, 0, sizeof a);
    }
};

Matrix operator* (Matrix a, Matrix b)
{
    Matrix c;
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 1; k <= m; k ++ )
                c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % P;
    return c;
}

int qmi(Matrix a, int b)
{
    Matrix res;
    for (int i = 1; i <= m; i ++ ) res.a[i][i] = 1;
    while (b)
    {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }

    int sum = 0;
    for (int i = 1; i <= m; i ++ ) sum += res.a[i][i];
    return sum % P;
}

int phi(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i ++ )
        if (n % i == 0)
        {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) res = res / n * (n - 1);
    return res % P;
}

int inv(int n)
{
    n %= P;
    for (int i = 1; i < P; i ++ )
        if (i * n % P == 1)
            return i;
    return -1;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, k;
        cin >> n >> m >> k;
        Matrix tr;
        for (int i = 1; i <= m; i ++ )
            for (int j = 1; j <= m; j ++ )
                tr.a[i][j] = 1;
        while (k -- )
        {
            int x, y;
            cin >> x >> y;
            tr.a[x][y] = tr.a[y][x] = 0;
        }
        int res = 0;
        for (int i = 1; i * i <= n; i ++ )
            if (n % i == 0)
            {
                res = (res + qmi(tr, i) * phi(n / i)) % P;
                if (i != n / i)
                    res = (res + qmi(tr, n / i) * phi(i)) % P;
            }
        cout << res * inv(n) % P << endl;
    }
    return 0;
}

在這里插入圖片描述

講完啦！六千字的題解，快寫死我了，你看懂了嘛？(●ˇ?ˇ●)

看不懂沒關系，點個贊就懂了 =￣ω￣=

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258990.html

標籤：其他

上一篇：CSDN開博三周年--回首向來蕭瑟處，鐵馬冰河入夢來

下一篇：案例:用python將中文翻譯的和英文原文合成新的word檔案