http://acm.hdu.edu.cn/showproblem.php?pid=3869

polya计数

题里给的环，可以从某个顶点开始，按照逆时针顺序，依次将经过的边权和点权构成一个序列，那么这个序列唯一确定这个环。并且，一切旋转，都相当于对形成的序列进行循环移位。因此可以用扩展KMP算法，将两个原序列拼接作为匹配串，将原序列作为模式串，就可以在O(N)内知道所有能和原串重合的移位方法。对于每个移位方法，对应于一种旋转。最后使用polya进行计数，对于每种旋转重合的k，其对应循环节长度为gcd(N,k)。最后公式就是对所有能旋转k次重合的k，result=sigma( C^gcd(N,k) )/(k的种类数)。

  1/*
  2    author: AmazingCaddy
  3    time:    2011/8/10   21:11
  4*/
  5#include <cstdio>
  6#include <complex>
  7#include <cstdlib>
  8#include <iostream>
  9#include <cstring>
 10#include <string>
 11#include <algorithm>
 12#include <cmath>
 13#include <ctime>
 14#include <vector>
 15#include <map>
 16#include <queue>
 17using namespace std;
 18
 19//typedef __int64 ll;
 20typedef long long ll;
 21
 22const int mod = 1000000007;
 23const int maxn = 100004;
 24
 25struct node
 26{
 27    int vec, edge;
 28    bool operator == ( const node & a ) const
 29    {
 30        return vec == a.vec && edge == a.edge;
 31    }
 32    bool operator != ( const node & a ) const
 33    {
 34        return !( *this == a );
 35    }
 36};
 37node pattern[ maxn ], text[ maxn << 1 ];
 38
 39ll powC[ maxn ];
 40int fail[ maxn ], vis[ maxn ];
 41int N, C;
 42
 43ll gcd( ll a, ll b ) { return ( b ? gcd( b, a % b ) : a ); }
 44
 45ll pow_mod( ll a, ll b )
 46{
 47    ll ans = 1, d = a % mod;
 48    while( b )
 49    {
 50        if( b & 1 ) ans = ans * d % mod;
 51        d = d * d % mod;
 52        b >>= 1;
 53    }
 54    return ans;
 55}
 56
 57ll Inv( ll n ) { return pow_mod( n, mod - 2 ); }
 58
 59void init( )
 60{
 61    powC[ 0 ] = 1;
 62    for( int i = 1; i <= N; i++ )
 63        powC[ i ] = powC[ i - 1 ] * C % mod;
 64}
 65
 66void faillink( )
 67{
 68    node * t = pattern;
 69    --t;
 70    for( int i = 1, j = 0; i <= N; i++, j++ )
 71    {
 72        fail[ i ] = j;
 73        while( j > 0 && t[ i ] != t[ j ] ) j = fail[ j ];
 74    }
 75    /*
 76    int j, k;
 77    flink[ 0 ] = -1;
 78    j = 1;
 79    while( j < N )
 80    {
 81        k = flink[ j - 1 ];
 82        while( k != -1 && pattern[ k ] != pattern[ j - 1 ] )
 83            k = flink[ k ];
 84        flink[ j ] = k + 1;
 85        j++;
 86    }
 87    */
 88}
 89
 90void kmp( )
 91{
 92    node *s = text, *t = pattern;
 93    --s, --t;
 94    for( int i = 1, j = 1; i <= 2 * N; i++, j++ )
 95    {
 96        while( j > 0 && s[ i ] != t[ j ] ) j = fail[ j ];
 97        if( j == N ) { vis[ i - N ] = 1; j = fail[ j ]; }
 98    }
 99    /*
100    int i = 0, j = 0;
101    while( i < N * 2 )
102    {
103        while( j != -1 && pattern[ j ] != text[ i ] )
104            j = flink[ j ];
105        if( j == N - 1 ) { vis[ i - N + 1 ] = 1; j = flink[ j ]; }
106        i++;
107        j++;
108    }
109    */
110}
111
112int main(int argc, char *argv[])
113{
114//    freopen( "in", "r", stdin );
115//    freopen( "out1", "w", stdout );
116    int cas;
117    scanf( "%d", &cas );
118    while( cas -- )
119    {
120        scanf( "%d%d", &N, &C );
121        init( );
122        for( int i = 0; i < N; i++ )
123            scanf( "%d", &pattern[ i ].vec );
124        for( int i = 0; i < N; i++ )
125            scanf( "%d", &pattern[ i ].edge );
126        for( int i = 0; i < N; i++ )
127            text[ i ] = text[ i + N ] = pattern[ i ];
128        faillink( );
129        memset( vis, 0, sizeof( vis ) );
130        kmp( );
131        ll ans = 0, cnt = 0;
132        for( int i = 1; i <= N; i++ )
133        {
134            if( vis[ i ] )
135            {
136                cnt++;
137                ans = ( ans + powC[ gcd( N, i ) ] ) % mod;
138            }
139        }
140        ans = ans * Inv( cnt ) % mod;
141        cout << ans << "\n";
142    }
143//    cerr << clock( ) << endl;
144    return 0;
145}
146