uva 10294 - Arif in Dhaka (First Love Part 2)(置换)

本文主要是介绍uva 10294 - Arif in Dhaka (First Love Part 2)(置换)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 10294 - Arif in Dhaka (First Love Part 2)

题目大意：项链和手镯都是由若珠子穿成的环形首饰，区别在于手镯可以翻转，但是项链不行。给定n和t，表示用t种颜色的n个珠子能制作的项链和手镯的个数。

解题思路：等价类计数，一共两种置换，旋转或者翻转。

• 旋转：枚举间距0,1,2,3…,n−1,所以不动点a=∑i=0n−1tgcd(n,i)
• 翻转：当n为奇数时，对称轴有n条，每条对称轴形成n−12个长度为2的循环和一个长度为1的循环，所以不动点b1=ntn+1/2;当n为偶数时，有两种对称轴，一种是穿过珠子的，一种是不穿过珠子的，都有n2条，但是形成的循环分别为n2−1个长度为2和两个长度为1，n2个长度为2，所以b2=n∗(tn/2+1+tn/2)2

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef unsigned long long ll;
const int maxn = 50;int gcd (int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int main () {int n, t;ll p[maxn];while (scanf("%d%d", &n, &t) == 2) {p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i-1] * t;printf("%lld\n", p[i]);}ll a = 0, b = 0;for (int i = 0; i < n; i++)a += p[gcd(n, i)];if (n&1)b = n * p[(n+1)/2];elseb = n / 2 * (p[n/2+1] + p[n/2]);printf("%lld %lld\n", a / n, (a + b) / 2 / n);}return 0;
}

这篇关于uva 10294 - Arif in Dhaka (First Love Part 2)(置换)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---