bzoj 4330: JSOI2012 爱之项链

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

听说这题不公开.. 那就不贴题意了

首先要用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 ;

 }