UVa 10294 (Pólya计数) Arif in Dhaka (First Love Part 2)
2024-10-19 12:32:49
Burnside定理:若一个着色方案s经过置换f后不变,称s为f的不动点,将置换f的不动点的数目记作C(f)。等价类的数目等于所有C(f)的平均值。
一个项链,一个手镯,区别在于一个能翻转一个不能,用t种颜色染n颗珠子,求等价类的个数。
旋转置换群一共有n个置换,分别对应将项链整体逆时针旋转0个、1个、2个...珠子的置换。
对于第i个置换,第0个、i个、2i...个珠子构成一个循环,共有gcd(n, i)个循环,每个循环中有n / gcd(n, i)个珠子。
所以n个置换,每个置换的不动点有tgcd(i, n)个。
对于翻转的置换群根据n的奇偶分两种情况:
- n为奇数,对称轴有n条,每条都穿过一个珠子,每个置换有(n+1)/2个循环,其中包括(n-1)/2个长度为2的循环和一个长度为1的循环(就是穿过的那个珠子)。所以不动点的总数为nt(n+1)/2
- n为偶数,有n/2条穿过珠子的对称轴,每个对称轴穿过两个珠子。共有n/2+1个循环,其中包括n/2-1个长度为2的循环 和 2个长度为1的循环;还有n/2条不穿过珠子的对称轴,共有n/2个长度为2的循环。
另 a = sum{ tgcd(m, i) | 0 ≤ i ≤ n-1 }
如果n为奇数,b = nt(n+1)/2
如果n为偶数,b = n/2 * (t(n/2+1) + tn/2)
则所求答案分别为 a/n 和 (a+b)/(2n)
#include <cstdio>
typedef long long LL; int gcd(int a, int b)
{ return b == ? a : gcd(b, a%b); } const int maxn = ;
LL p[maxn]; int main()
{
//freopen("in.txt", "r", stdin); p[] = ;
int n, t;
while(scanf("%d%d", &n, &t) == )
{
for(int i = ; i <= n; i++) p[i] = p[i-] * t;
LL a = , b = ;
for(int i = ; i < n; i++) a += p[gcd(n, i)];
if(n & ) b = n * p[(n+)/];
else b = n/ * (p[n/+] + p[n/]);
printf("%lld %lld\n", a/n, (a+b)/n/);
} return ;
}
代码君
最新文章
- java中文文档官方下载
- 【译】RabbitMQ:远程过程调用(RPC)
- Lua模块测试
- nginx 一二事(3) - 反向代理以及负载均衡
- 使用Spring Profile和Mybatis进行多个数据源(H2和Mysql)的切换
- hdu 1520 (树形DP)
- 谈NOT IN和Exists
- apache archiva安装教程
- unix系统非roo账号安装JDK
- sql和shell注入测试
- Effective Java:Ch4_Class:Item14_在public类中应该使用访问方法而不是public域
- C# foreach 值类型及引用类型迭代变量改变的方式
- Django之如何预防csrf功能的方式 form提交与ajax提交
- python学习笔记02--列表和元组
- 倍福TwinCAT3上位机与PLC通信测试(ADS通信) 包含C#和C++代码
- Linux下安装微信(转)
- redis滴
- 防范跨站脚本攻击(XXS)的关键手段
- Reactor与Proactor比较
- 实习第二天-String对象的不可变性-未解决