UVA 10294 Arif in Dhaka (置换polya)

UVA 10294 Arif in Dhaka (置换polya)

【题目链接】：​​click here~~​​

【题目大意】：

给你一串珠子（连接成了一个环），共有n个珠子组成，你有t种颜色，现在你来给这个珠子染色，问染成项链有多少种方法？染成手镯有多少种方法？在项链里，经过顺时针旋转后相同的算一个，在手镯里，经过顺时针旋转或者沿着对称轴兑换后一样的算一个。即不同之处在于项链不能够反转，而手镯可以反转。

【思路】：

首先，我们来看看两个很有用的关于置换的定理，第一个就是Burnside 描述为：对于置换f，一种着色方案s经过一种置换后不变，则称这种着色方案s是f的不动点。若将f的不动点计为C（f），则可以证明等价类数目为所有C（f）的平均值。 一般用这个引理就可以解决所有的问题了。 而Polya定理是这样给出的：如果置换f可以分解成m（f）个循环的乘积，那么每个循环内的颜色必须相同（必须的，不信则可以自己试验一下），假设有t中颜色，那么C（f）= t^（m（f）），则等价类数目也可求得。 而这个题目就是非常经典的置换的题目（等价统计类问题），只不过对于手镯来说，你就要注意手镯是可以旋转，也可以翻转的，所以最后是要加上旋转的数目，并且奇偶是不同的两种情况。 一共有两种置换：旋转和翻转，其中项链只有第一种，而手镯两种都有，假定所有珠子按照逆时针编号：0~n-1.

旋转：如果逆时针旋转i颗珠子的间距，则珠子0，i,2i,,,构成一个循环，这个循环共有n/gcd(i,n),为什么？留给读者自己思考，那么由对称性，所有循环节的长度均是相同的，因此一共有gcd(i,n)个循环，总数为：a=fac[i] = t^gcd(i ,n) 翻转：当n&1:对称轴有n条，每条对称轴形成(n-1)/2个长度为2的循环和1个长度为1的循环，即（n+1）/2个循环，则总数为b=n*t^(n+1)/2;

当n为偶数，有两种对称轴：穿过珠子的有(n/2)条，形成(n/2-1)个长度为2的循环和两个长度为1的循环；不穿过珠子的有（n/2）条，形成（n/2）个长度为2 的循环，则总数为b=n/2*(t^(n/2+1)+t^(n/2));

最后根据Polya定理：项链数为a/n,手镯数为(a+b)/2*n;

代码：

#include using namespace std;typedef long long LL;int gcd(int a,int b){return b==0?a:gcd(b,a%b);}LL fac[100000009];int n,t;LL a,b;int main(){ fac[0]=1; while(scanf("%d%d",&n,&t)==2&&n){ a=b=0; for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*t; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。