[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;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
