首页 > ACM题库 > HDU-杭电 > HDU 3869-Color the Simple Cycle-组合数学-[解题报告]HOJ
2015
04-13

HDU 3869-Color the Simple Cycle-组合数学-[解题报告]HOJ

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;



}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u010510549/article/details/38460129