POJ2865 Birthday toy[Polay+矩阵快速幂优化dp]

$Birthdaytoy$Birthday toy

$Description$Description
有一个 $n$n个珠子的环，中心还有一颗珠子，用 $k$k种颜色来染。要求相邻珠子的颜色不同，中心珠子的颜色不能和外围任意一颗珠子的颜色一样，考虑旋转，问本质不同的珠子个数？

做这道题之前推荐先看一下这道题

$最初想法$最初想法
中间的珠子颜色提前分配就好, $以下颜色数量M均经过减一操作.$以下颜色数量M均经过减一操作.
对于置换 $\mathrm{\"}旋转k次\mathrm{\"}$"旋转k次", 方案数量为 $M\ast (M-1)\ast ...\ast (M-2)$M∗(M−1)∗...∗(M−2), 按这个方法计算就可以了 .

错因是到 $i-1$i−1 时, 在前面计算出来的方案数中既包含 $i-2$i−2 与 $1$1 相同的方案数, 也包含不同的方案数,
于是当前 $i-1$i−1 的选择并不是 $M-2$M−2 种 .

$正解部分$正解部分
设 $F\left[i\right]$F[i] 表示 $i$i 个元素成环时的方案数量,
假设已经知道了 $F[i-1],F[i-2]$F[i−1],F[i−2], 考虑推出 $F\left[i\right]$F[i],

1. 由于 $F[i-1]$F[i−1]表示在 $i-1$i−1 与 $1$1 的颜色不同的前提下 $i-1$i−1 的方案,
   此时的 $i$i 有 $M-2$M−2 种选择,
   $\therefore i-1$∴ i−1 与 $i$i 颜色不同时, $F\left[i\right]+=F[i-1]\ast (M-2)$F[i] +=F[i−1]∗(M−2)

2. 那么 $i-1$i−1 与 $i$i 颜色相同的方案数量呢 ?
   
   由于 $i-1$i−1 与 $1$1 的颜色相同, $F[i-2]$F[i−2] 又表示 $i-2$i−2 与 $1$1 颜色不同的方案数量, 间接也表示了 $i-2$i−2 与 $i-1$i−1 的颜色也不同, 将 $i-1$i−1 插入 $i-2$i−2 后面, 满足了邻位不同, 且 $i$i与 $i-1$i−1相同的条件,
   
   此时 $i$i 有 $M-1$M−1 种选择
   $\therefore i-1$∴ i−1 与 $i$i 颜色相同时, $F\left[i\right]+=F[i-2]\ast (M-1)$F[i] +=F[i−2]∗(M−1) .

$\therefore 综上所述F\left[i\right]=(M-2)\ast F[i-1]+(M-1)\ast F[i-2]$∴ 综上所述   F[i]=(M−2)∗F[i−1]+(M−1)∗F[i−2]

有点像斐波那契数列是吧?
于是可以使用 矩阵快速幂 优化.

最后枚举约数, 用 $Polya$Polya求解即可, 具体点击这里查看拓展2 .

时间复杂度 $O\left(\sqrt{N}logN\right)$O(N ​logN) .

$实现部分$实现部分
没什么好说的 , 给出代码供参考.

#include<cstdlib>
#include<cstdio>
#include<cstring>
#define reg register

const int mod = 1000000007;

int N;
int M;
int Tmp_2;
int Tmp_3;
//{{{
struct Matrix{
        int C[4][4];
        Matrix(){ memset(C, 0, sizeof C); }
} A, B, C;

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

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

int KSM_1(int a, int b){
        a %= mod;
        int s = 1;
        while(b){
                if(b & 1) s = 1ll*s*a % mod;
                a = 1ll*a*a % mod;
                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;
}
//}}}
void Calc(int &Ans, int d){
        if(d == 2){
                Ans = ((1ll*phi(N/d)*Tmp_2)%mod + 1ll*Ans) % mod;
                return ;
        }
        else if(d == 3){
                Ans = ((1ll*phi(N/d)*Tmp_3)%mod + 1ll*Ans) % mod;
                return ;
        }
        B = KSM(A, d-3);
        int t = (1ll*B.C[1][1]*Tmp_3%mod + 1ll*B.C[2][1]*Tmp_2%mod) % mod;
        int tmp = (1ll*t*phi(N/d)) % mod;
        Ans = (1ll*Ans + tmp) % mod;
}

void Work(){
        M --;
        A.C[1][1] = M-2, A.C[1][2] = 1;
        A.C[2][1] = M-1, A.C[2][2] = 0;
        Tmp_2 = 1ll*(M%mod) * (M-1) % mod;
        Tmp_3 = 1ll*M%mod * (1ll*M-1)%mod;
        Tmp_3 = 1ll*Tmp_3 * (M-2) % mod;
        int Ans = 0;
        for(reg int d = 1; d*d <= N; d ++){
                if(N % d) continue ;
                if(d != 1) Calc(Ans, d);
                int d1 = N/d;
                if(d1 == d) continue ;
                Calc(Ans, d1);
        }
        int tmp = (M+1) % mod;
        Ans = 1ll*Ans*tmp % mod;
        Ans = 1ll*Ans*KSM_1(N, mod-2)%mod;
        printf("%d\n", Ans);
}

int main(){
        while(~scanf("%d%d", &N, &M)) Work();
        return 0;
}