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

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

UVA 10294 - Arif in Dhaka (First Love Part 2)

题目链接

题意：给定n个珠子，t种颜色， 问能组成几个项链和手镯（手镯能翻转，项链不能）

思路：利用Burnside求解，推理出旋转的循环个数是gcd(i, n)，翻转的分为奇偶情况考虑

代码：

#include <stdio.h>
#include <string.h>const int N = 30;
int t, next[N], vis[N], num[N];
char str[N];bool judge() {for (int i = 2; i <= 26; i += 2)if (num[i] % 2) return false;return true;
}int main() {scanf("%d", &t);while (t--) {scanf("%s", str);for (int i = 0; i < 26; i++)next[i] = str[i] - 'A';memset(vis, 0, sizeof(vis));memset(num, 0, sizeof(num));for (int i = 0; i < 26; i++) {if (!vis[i]) {vis[i] = 1;int t = next[i];int cnt = 1;while (!vis[t]) {vis[t] = 1;t = next[t];cnt++;}num[cnt]++;}}printf("%s\n", judge()?"Yes":"No");}return 0;
}

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

---