http://poj.org/problem?id=2154 大致题意：由n个珠子，n种颜色，组成一个项链。要求不同的项链数目，旋转后一样的属于同一种，结果模p。 n个珠子应该有n种旋转置换，每种置换的循环个数为gcd(i,n)。如果直接枚举i，显然不行。但是我们可以缩小枚举的数目。改为枚举每个循环节的长度L，那么相应的循环节数是n/L。所以我们只需求出每个L有多少个i满足gcd（

NYOJ 280 LK的项链  :click here POJ 2409 Let it Bead:click here 题意：一盒有红、蓝、绿三种颜色的珠子，每种颜色珠子的个数都大于24，现在LK想用这一盒珠子穿出一条项链，项链上的珠子个数为n（0<=n&lt;=24）,请你帮她计算一下一共可以用这一盒珠子可以穿出多少条不同的项链。通过旋转、翻转达到同一种状态的被认为是相同的项链。

题目描述： 给你一个数字序列（每个数字唯一），每次你可以交换任意两个数字，代价为这两个数字的和，问最少用多少代价能把这个序列按升序排列好。 题目的具体做法是参考刘汝佳的《算法艺术与信息学奥赛》大概思路是：以后再用别种方法解， 1.找出初始状态和目标状态。明显，目标状态就是排序后的状态。 2.画出置换群，在里面找循环。例如，数字是8 4 5 3 2 7 明显，

和1286一样，裸polya，可以在吉大模板找到，polya可能要看一会儿 #include <cstdio>#include <cmath>#include <iostream>using namespace std;long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}int main(){#if

很裸的polya，不过我看polya看了很久 吉大ACM模板里面也有 #include <cstdio>#include <cmath>#include <iostream>using namespace std;long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}int main(){#ifnd

题目来源：UVa 10294 Arif in Dhaka (First Love Part 2) 题意：n颗珠子t种颜色 求有多少种项链和手镯 项链不可以翻转 手镯可以翻转 思路：Polya定理  题目就是求等价类 项链只能旋转 手镯可以旋转也可以翻转 根据定理 等价类的数量等于各个置换f的t^m(f)的平均数 m(f)是置换的循环节数 下面每次t^x x都是循环节数 下面考虑手镯 旋转翻

题目链接：hdu 4633 Who’s Aunt Zhang 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int mod = 10007;int inv24, P[100];int pow_mod(int x, int n, int mod) {int ret =

Burnside引理 设G是N{1,2，.....，n}上的置换群，G在N上可引出不同的等价类（在置换群中有置换的都等价），其不同的等价类的个数为LL=1/|G|*（c1(a1)+...c1(ai)...+c1(ag)）c1表示置换ai作用过后不变的方案数，也就是置换中循环节长度是1的循环个数（N中的元素是组合方案的序号不是自然数！此置换群是关于所有着色图像（所有可能的情况）集合N的置换）Bur

Burnside引理 设G是N={1，2，……，n}上的置换群，G在N上可引出不同的等价类，其中不同的等价类的个数为 1|G|∑g∈G \frac{1}{|G|}\sum_{g∈G}c1(g)，其中，c1(g)是置换g中不边缘的个数，即g中1阶循环的个数。 理解 后续补更…… polya定理 设G={a1,a2,a3,……,ag}是n个对象的置换群，用m种颜色给这n个对象染色，不同的着色

前言 本文对于群论的讨论范围仅限于ACM和OI（算法竞赛与信息学竞赛），并且内容比较基础，以证明为主，零基础读懂本文需要积极思考。 本文对于四大定理的讨论以基本概念理解为主。由于本部分变化略大，具体实现待我题量积累一下之后再给出。 1.群基础概念 1.1群定义及概念 1.1.1什么是群 给定一个集合和集合上的二元运算,如果满足以下条件： （1）封闭性。对于任意的成立。 （2）结合律