本文主要是介绍UVa 10294 Arif in Dhaka (First Love Part 2) Polya定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：UVa 10294 Arif in Dhaka (First Love Part 2)
题意：n颗珠子t种颜色 求有多少种项链和手镯 项链不可以翻转 手镯可以翻转
思路：Polya定理 题目就是求等价类 项链只能旋转 手镯可以旋转也可以翻转
根据定理 等价类的数量等于各个置换f的t^m(f)的平均数 m(f)是置换的循环节数 下面每次t^x x都是循环节数
下面考虑手镯 旋转翻转都算
对于旋转 可以旋转0，1，...，n-1 每一个置换的循环节为gcd(0,n), gcd(1,n), ..., gcd(n-1,n)
所以等价类为t^gcd(0,n) + t^gcd(1,n)+ ...+t^gcd(n-1,n) = a 设为a
t是输入的颜色数量 这里没有除以置换的数量 最后算完翻转在除
对于翻转 分奇数和偶数
奇数
翻转只能拿住一个点翻转 可以拿住n个点的任何一个 等价类为n*t^(n/2+1) = b 设为b 拿住的那一个点自己就是一个循环节 剩下的2个一组为循环节
偶数
可以拿住两个点 或者不拿 拿住2个点有n/2*t^(n/2+1) 拿住的两个点是2个为1的循环节 剩下的2个一组为循环节 n/2是去重 选的两个点连起来是对称轴
可以不拿 n/2*t^(n/2) 2个一组为循环节 n/2*(t^(n/2+1)+t^(n/2)) = b设为b
最后还要求平均数 除以所有置换的数量
旋转和翻转的置换数量为n+n=2n 答案为(a+b)/2/n
#include <cstdio>
#include <cstring>
typedef long long LL;
const int maxn = 55;
LL a[maxn];
LL gcd(LL a, LL b)
{return b ? gcd(b, a%b) : a;
}
int main()
{int n, m;while(scanf("%d %d", &n, &m) != EOF){a[0] = 1;for(int i = 1; i <= n; i++){a[i] = a[i-1] * m;}LL x = 0, y = 0;for(int i = 1; i <= n; i++){x += a[gcd(i, n)];}if(n&1){y = a[(n+1)/2]*n;}else{y = (a[n/2] + a[n/2+1])*n/2;}printf("%lld %lld\n", x/n, (x+y)/2/n);}return 0;
}
这篇关于UVa 10294 Arif in Dhaka (First Love Part 2) Polya定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
