听说这题不公开.. 那就不贴题意了
首先要用burnside引理求出戒指的种数，那么对于一个顺时针旋转$k$个位置的置换就相当于连上一条$(i,(i+k)%R)$的边，每个环颜色必须相同
环的个数为$gcd(k,R)$，所以这样的方案数就有$R^{gcd(k,R)}$种
然后dp求项链的方案数，设$g_{i,0}$表示$1$和$i$不同，中间相邻不同的方案数，$g_{i,1}$表示$1$和$i$相同，中间相邻不同的方案数
那么有如下推导：
$$g_{i,0}=(i-1)g_{i-1,1}+(i-2)g_{i-1,0}$$
$$g_{i,1}=g_{i-1,0}$$
再化一下：$$g_{i,0}=(i-1)g_{i-2,0}+(i-2)g_{i-1,0}$$
由于我们需要的也就是$g_{i,0}$，不妨设$f_i=g_{i,0}$，所以：$$f_i=(i-1)f_{i-2}+(i-2)f_{i-1}$$
这就可以用矩阵乘法优化 听说有通项公式
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
const LL Mod = ;
const LL Maxn = ;
LL n, m, r;
LL gcd ( LL a, LL b ){
if ( a == ) return b;
return gcd ( b%a, a );
}
LL pow ( LL x, LL k ){
LL ret = ;
while (k){
if ( k & ) ret = (ret*x)%Mod;
x = (x*x)%Mod;
k >>= ;
}
return ret;
}
struct matrix {
LL a[][];
LL l1, l2;
void clear (){ memset ( a, , sizeof (a) ); }
}trans, x, z, fi;
matrix ttimes ( matrix x, matrix y ){
matrix ret;
ret.clear ();
ret.l1 = x.l1; ret.l2 = y.l2;
LL i, j, k;
for ( i = ; i < ret.l1; i ++ ){
for ( j = ; j < ret.l2; j ++ ){
for ( k = ; k < x.l2; k ++ ){
ret.a[i][j] = ( ret.a[i][j] + (x.a[i][k]*y.a[k][j])%Mod ) % Mod;
}
}
}
return ret;
}
LL phi ( LL x ){
LL ret = x, sq = sqrt (x);
for ( LL i = ; i <= sq; i ++ ){
if ( x % i == ){
ret = ret/i*(i-);
while ( x % i == ) x /= i;
}
}
if ( x > ) ret = ret/x*(x-);
return ret;
}
int main (){
LL i, j, k;
scanf ( "%lld%lld%lld", &n, &m, &r );
LL o = , sq = sqrt (m);
for ( i = ; i <= sq; i ++ ){
if ( m % i == ){
o = (o+(pow(r,i)*phi(m/i))%Mod)%Mod;
if ( i*i == m ) continue;
o = (o+(pow(r,m/i)*phi(i))%Mod)%Mod;
}
}
LL inv = pow ( m, Mod- );
o = (o*inv)%Mod;
if ( n == ){ printf ( "0\n" ); return ; }
trans.l1 = trans.l2 = ;
trans.a[][] = o-; trans.a[][] = ; trans.a[][] = o-;
x = trans;
z.l1 = z.l2 = ;
z.a[][] = ; z.a[][] = ;
for ( i = n-; i >= ; i >>= ){
if ( i & ) z = ttimes ( z, x );
x = ttimes ( x, x );
}
fi.l1 = ; fi.l2 = ;
fi.a[][] = (o*(o-))%Mod;
fi = ttimes ( fi, z );
printf ( "%lld\n", fi.a[][] );
return ;
}