上次那个项链问题我找到原题了-----------大家来讨论一下 - C语言论坛

楼主

问题点数：0 回复次数：8

上次那个项链问题我找到原题了-----------大家来讨论一下

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1110

Latin Stones

时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:539 测试通过:75

描述

Ray is very excited today because Jiejie has finally agreed to give Ray some precious Latin Stones. The stones are all the same except for their colors. Every single stone has only one color and there are seven colors in all (Rumba, Samba, ChaChaCha, Jive, Paso Doble, Waltz, and FoxStep).

Since these stones are very precious, Jiejie would like Ray to keep them in an elegant way that obeys the following rules:

1. Stones must be placed in a circle and the length of the circle is n.

2. Adjacent stones cannot have the same color.

This problem really puzzles Ray and he even doubts whether there is a feasible way. So he asks you for help. Given the length of the circle, you should calculate how many different ways the stones can be arranged (ways that can be obtained by rotations should be counted as one). Assume the number of stones of each color is sufficient.

输入

There are multiple test cases. For each test case there is only one line that contains an integer n (less than 100,000) indicating the length of the circle.

输出

For each test case output one integer: the number of ways. Since this number can be really large, just output the reminder after being divided by 2003.

样例输入

样例输出

题目来源

NUAA

搜索更多相关主题的帖子: 内存　项链　 align　left　

第 2 楼

得分:0

这不是今年南京赛区预赛的题目嘛，没做出来

第 3 楼

得分:0

就是啊....
我也没有做出来....貌似当时他们快的要命..你能找到报告不??

第 4 楼

得分:0

今天正直南京正式比赛...呵呵

第 5 楼

得分:0

我的想法是先推出一个递推公式把不考虑旋转重复的排列算出来，再用polya原理。

事实上我已经得到了一个递推公式


int dp[1000001][2];
void init_dp()
{
    dp[2][0]=1;
    dp[2][1]=0;
    dp[3][0]=5;
    dp[3][1]=0;
    for(int i=4;i<=1000000;i++){
        dp[i][0]=5*(dp[i-1][0]+dp[i-1][1]);
        dp[i][1]=6*(dp[i-2][0]+dp[i-2][1]);
    }    
}   
int redundancy(int n)
{
    if(n==1)return 7;
    return 7*6*(dp[n][0]+dp[n][1]);
}

redundancy(n)将返回带有重复的排列数，我不知道这个公式是否正确，你可以验证一下。至于模2003如何处理我也没想好。

从redundancy(n)得到考虑重复的排列数我的想法是，
先定义一下旋转i的概念，旋转i表示：把1置换到1+i的位置，2置换到2+i，...
因此，旋转0是不变化，旋转n等价于旋转0，等等
按照polya计数原理，考虑重复的排列数=Avg{旋转i的等价排列数,i=0,1,2...n-1}
旋转i使得x个排列等价,x>0当切仅当n%i==0(i!=1,i=0的情况可以用i=n的情况处理)
而n%i==0时的等价排列数正是redundancy(i)

但是这样算出来到输入为8的时候出现了除不尽的情况，显然是哪里出了问题，我没有找到问题在哪

第 6 楼

得分:0

你可以看到当n=8的时候出现了除不尽

程序代码：


#include <iostream>
using namespace std;
double dp[1000001][2];
void init_dp()
{
    dp[2][0]=1;
    dp[2][1]=0;
    dp[3][0]=5;
    dp[3][1]=0;
    for(int i=4;i<=1000000;i++){
        dp[i][0]=5*(dp[i-1][0]+dp[i-1][1]);
        dp[i][1]=6*(dp[i-2][0]+dp[i-2][1]);
    }    
}   
double redundancy(int n)
{
    if(n==1)return 7;
    return 7*6*(dp[n][0]+dp[n][1]);
}    
double fun(int n)
{
    double res=0;
    for(int i=2;i<=n/2;i++){
        if(n%i==0){
            res+=redundancy(i);
        }    
    }
    return res+redundancy(n);
}
int main()
{
    init_dp();
    int n;
    while(scanf(\"%d\",&n)!=EOF){
        printf(\"%lf\n\",fun(n)/n);
    }    
}

第 7 楼

得分:0

这里加了一个约束条件使得有一些置换是不满足的...似乎你是在这里出了问题

第 8 楼

得分:0

以下是引用crackerwang在2007-10-28 16:51:50的发言：

这里加了一个约束条件使得有一些置换是不满足的...似乎你是在这里出了问题

你举例说明

第 9 楼

得分:0

我也说不太清楚...因为本身我自己也不会...