首页 > 搜索 > DFS搜索 > HDU 1817 Necklace of Beads-DFS-[解题报告] C++
2013
12-23

HDU 1817 Necklace of Beads-DFS-[解题报告] C++

Necklace of Beads

问题描述 :

Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < 40 ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?

输入:

The input has several lines, and each line contains the input data n.
-1 denotes the end of the input file.

输出:

The output should contain the output data: Number of different forms, in each line correspondent to the input data.

样例输入:

4
5
-1

样例输出:

21
39

Polya定理:

       设G是一个p个对象的置换群,那么用k种颜色对p个对象进行染色!当一种方案在群G的作用下变为另外一种方案,那么我们这个时候就认为这两个方案是一样的。那么在这种规定下不同的染色方案为:

n=(Ek^m(f))/|G|,其中m(f)是置换f的循环节。

       Polya定理是基于Burnside定理和另外一个定理的,其中Burnside定理的通俗表达方法如下:

      1)如果令C(f)表示在置换f的作用下,本质不变的着色方案数!那么可以证明的是“本质不同的着色方案数就是所有置换f下的C(f)的平均数”。

       在Burnside的基础上,我们在介绍一个定理:

       2)如果使用k种颜色给有限集合S着色,那么对于一个置换f,在该置换下本质不变的着色方案数就是C(f)=k^(m(f)),其中m(f)是置换f的循环节数。

       基于上面的1)2)两个定理,便很明显的得到Polya定理。

       介绍了Polya定理之后,我们来看看Polya的简单应用,在POJ 1286题中,如果是旋转或者是对称变换相同的着色方案算作一种着色方案数。那么我们直接使用Polya定理进行求解就行了,但是这个时候对奇数和偶数的情况下对称变换的置换是不一样的,分开求解就可以了!对于旋转的置换的循环节我们直接进行dfs求解就可以了。

       

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
LL myPow(LL a,int b)
{
    LL sum=1LL;
    while(b)
    {
        if(b%2==1)
        {
            sum*=a;
        }
        a*=a;
        b/=2;
    }
    return sum;
}

int vis[30],adj[30];

void dfs(int i)
{
    if(vis[i]==0)
    {
        vis[i]=1;
        dfs(adj[i]);
    }
}

int find(int s,int n)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        int e=(s+i-1)%n;
        if(e==0)
            e=n;
        adj[i]=e;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            dfs(i);
            sum++;
        }
    }
    return sum;
}

int main()
{
    int n;
    LL a,b;
    while(scanf("%d",&n))
    {
        if(n==-1)
            break;
        if(n<=0)
        {
            printf("0\n");
            continue;
        }
        if(n%2==0)
        {
            a=myPow(3LL,n);
           for(int i=2;i<=n;i++)
           {
               int tn=find(i,n);
               a+=myPow(3LL,tn);
           }
            b=(LL)n;
            a=a+(LL)(n/2)*(myPow(3LL,(n+2)/2));
            a=a+(LL)(n/2)*(myPow(3LL,n/2));
            b+=(LL)n;
        }
        else
        {
            a=myPow(3LL,n);
            for(int i=2;i<=n;i++)
            {
                int tn=find(i,n);
                a+=myPow(3LL,tn);
            }
            b=(LL)n;
            a=a+(LL)n*(myPow(3LL,1+(n-1)/2));
            b+=(LL)n;
        }
        printf("%lld\n",a/b);
    }
    return 0;
}

下面附上我的代码:


解题报告转自:http://blog.csdn.net/geniusluzh/article/details/6795412


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。