Latin Stones
总提交: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.
样例输入
2
样例输出
21
题目来源
NUAA
----------------解决方案--------------------------------------------------------
这不是今年南京赛区预赛的题目嘛，没做出来
----------------解决方案--------------------------------------------------------
就是啊....
我也没有做出来....貌似当时他们快的要命..你能找到报告不??
----------------解决方案--------------------------------------------------------
今天正直南京正式比赛...呵呵
----------------解决方案--------------------------------------------------------
我的想法是先推出一个递推公式把不考虑旋转重复的排列算出来，再用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的时候出现了除不尽的情况，显然是哪里出了问题，我没有找到问题在哪
----------------解决方案--------------------------------------------------------
你可以看到当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);
}
}
----------------解决方案--------------------------------------------------------
这里加了一个约束条件使得有一些置换是不满足的...似乎你是在这里出了问题
----------------解决方案--------------------------------------------------------
这里加了一个约束条件使得有一些置换是不满足的...似乎你是在这里出了问题
你举例说明
----------------解决方案--------------------------------------------------------
我也说不太清楚...因为本身我自己也不会...
----------------解决方案--------------------------------------------------------