[Uva10294]Arif in Dhaka

标签： 置换 Burnside引理

---

题目链接

题意

有很多个珠子穿成环形首饰，手镯可以翻转和旋转，项链只能旋转。（翻转过的手镯相同，而项链不同）

有n个珠子，k种颜色，输出不同的项链和手镯的个数。

题解

• 先考虑旋转的置换：
  
  假如旋转i颗珠子，那么显然产生的循环节个数为gcd(i,n)，那么就可以做了。

• 考虑翻转的置换：
  
  首先可以知道，如果先旋转再翻转，肯定可以找到某一种翻转的置换与之等价。

  那么假如珠子的个数为奇数，可以得到（n/2）个长度为2的循环，一个长度为1的循环。
  
  假如是偶数，那么还需要分情况讨论：

  • 如果对称轴不穿过任一珠子，那么会分成（n/2）个长度为2的循环；

  • 如果穿过珠子，就会分成（n/2-1）个长度为2的循环和2个长度为1的循环；

Code

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<set>

#include<queue>

#include<map>

#include<stack>

#include<vector>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)

inline int read()

{

    int sum=0,p=1;char ch=getchar();

    while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();

    if(ch=='-')p=-1,ch=getchar();

    while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();

    return sum*p;

}

const int maxn=120;

int n,t;

ll power[maxn];

void doing()

{

	ll A=0,B=0;

	power[0]=1;

	REP(i,1,n)power[i]=power[i-1]*t;

	REP(i,1,n)A+=power[__gcd(i,n)];

	if(n & 1)B=n*power[n/2+1];

	else B=n/2*(power[n/2]+power[n/2+1]);

	cout<<A/n<<" "<<(A+B)/2/n<<endl;

}

int main()

{

	while(scanf("%d%d",&n,&t)==2)

	{

		doing();

	}

    return 0;

}