有一个个珠子的环,中心还有一颗珠子,用种颜色来染。要求相邻珠子的颜色不同,中心珠子的颜色不能和外围任意一颗珠子的颜色一样,考虑旋转,问本质不同的珠子个数?
中间的珠子颜色提前分配就好,
对于置换 , 方案数量为 , 按这个方法计算就可以了 .
错因是到 时, 在前面计算出来的方案数中既包含 与 相同的方案数, 也包含不同的方案数,
于是当前 的选择并不是 种 .
设 表示 个元素成环时的方案数量,
假设已经知道了 , 考虑推出 ,
-
由于 表示在 与 的颜色不同的前提下 的方案,
此时的 有 种选择,
与 颜色不同时, -
那么 与 颜色相同的方案数量呢 ?
由于 与 的颜色相同, 又表示 与 颜色不同的方案数量, 间接也表示了 与 的颜色也不同, 将 插入 后面, 满足了邻位不同, 且与相同的条件,
此时 有 种选择
与 颜色相同时, .
有点像斐波那契数列是吧?
于是可以使用 矩阵快速幂 优化.
最后枚举约数, 用求解即可, 具体点击这里查看拓展2 .
时间复杂度 .
没什么好说的 , 给出代码供参考.
#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
", Ans);
}
int main(){
while(~scanf("%d%d", &N, &M)) Work();
return 0;
}