2015
04-13

# Color the Simple Cycle

Consider a simple cycle with N vertices numbered from 1 to N. Each vertex and Each edge has an integer value. We use v[k] to represent the kth vertex’s value, and e[k] to represent the kth edge’s value. The kth edge is the edge of the kth and the (k+1)th vertex (the (N+m)th vertex is the mth vertex). Now we will use C different colors to color the graph. Every vertice will be colored by one of the C colors. If there exists some integer number k which satisfies v[i]=v[i+k] and e[i]=e[i+k] for each i from 1 to N(v[N+t]=v[t] and e[N+t]=e[t]), we call the graph is the same under k rotation.
If two ways of coloring the cycle can be the same with some rotation and under that rotation the color of the corresponding vertices are also the same, we consider the two ways are the same ways. Given the simple cycle and the number of colors we will use, how many different ways to color the cycle?

First comes an integer T representing the number of test cases. Each case consists of three lines. First line contains N(1<=N<=100000) and C (1<=C<=1000000). Second line contains N integer numbers representing the vertex’s values. The last line of each case contains N integer numbers representing the edge values. Each value is between 1 and 1000000.

First comes an integer T representing the number of test cases. Each case consists of three lines. First line contains N(1<=N<=100000) and C (1<=C<=1000000). Second line contains N integer numbers representing the vertex’s values. The last line of each case contains N integer numbers representing the edge values. Each value is between 1 and 1000000.

2
3 1
1 1 1
2 2 2
3 2
1 1 1
2 2 2

1
4

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const long long N = 1000050;
const long long M = 1000000007;
long long next[N];
long long n;
struct p
{
long long v,e;

bool operator == (const p & s){
if(v == s.v && e == s.e) return true;
return false;
}
}a[N];
long long power1(long long c,long long n)
{
long long res = 1;
while(n){
if(n&1) res *= c;
if(res >= M) res %= M;
c *= c;
if(c >= M) c %= M;
n >>= 1;
}
return res;
}
int getnext()
{
int len = n;
int i  = 0,j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || a[i] == a[j]){
++i,++j;
next[i] = j;
}else j = next[j];
}
next[len] = len - next[len];
if( (n % next[len])== 0) return next[len];
else return n;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int main(){
// freopen("in","r",stdin);
long long t,c,v,e;
scanf("%I64d",&t);
while(t--){
scanf("%I64d%I64d",&n,&c);
for(int i = 0;i < n ; ++i) {
scanf("%I64d",&a[i].v);
}
for(int i = 0; i < n; ++i){
scanf("%I64d",&a[i].e);
}
if(n == 1) {
printf("%I64d\n",c);
continue;
}
long long index = getnext();
long long ans = 0,num = 0;
for(int i = 1; i <= n; ++i) {
if(i % index != 0) continue;
ans += power1(c, gcd(i, n));
if(ans >= M) ans -=M;
++num;
}
printf("%I64d\n",(ans * power1(num,M- 2))%M);
}
return 0;

}