首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。