【uva 10294】 Arif in Dhaka (First Love Part 2) (置换,burnside引理|polya定理)
2024-10-19 11:46:02
题目来源:UVa 10294 Arif in Dhaka (First Love Part 2)
题意:n颗珠子t种颜色 求有多少种项链和手镯 项链不可以翻转 手镯可以翻转
【分析】
要开始学置换了。
置换是什么呢?
置换的广义概念在不同语境下有不同的形式定义:
在组合数学中,置换一词的传统意义是一个有序序列,其中元素不重复,但可能有阙漏。例如1,2,4,3可以称为1,2,3,4,5,6的一个置换,但是其中不含5,6。此时通常会标明为“从n个对象取r个对象的置换”。
置换的乘法:
f={1,3,2} g={2,1,3} f*g={2,3,1}
计算过程是 1->1->2, 2->3->3 , 3->2->1 。
置换的循环移位 (1 4 3)表示1->4, 4->3, 3->1。
比如 (1 2 3 4 5)
(3 5 1 4 2) =(1 3)(2 5)(4)
循环节为3.
等价类计数问题
题目定义一种等价关系,满足等价关系的元素被看成是同一类,只统计一次。等价关系满足自反性、对称性、传递性。
burnside引理
对于一个置换f,若一个着色方案s经过置换后不变,称s为f的不动点。(即循环里面只有一个元素)
将f的不动点数目记为C(f),则可以证明等价类数目为所有C(f)的平均值。
这题用到burnside引理或polya定理。(polya定理可以用burnside引理证明)
本题:
旋转:
如果逆时针旋转i颗珠子的间距,那么珠子0,i,2*i...构成一个循环。这个循环有n/gcd(i,n)个元素,根据对称性,所有循环长度均相同,因此一共有gcd(i,n)个循环。这些置换的不动点总数为a=sigma(t^gcd(i,n))。
翻转:
分两种情况讨论。当n为奇数时,对称轴有n条,。。。。不动点总数为$n*t$^$\dfrac{n+1}{2}$
当n为偶数是时,有两种对称轴,一共n条,。。。。不动点总数为$\dfrac{n}{2}*(t$^$(\dfrac{n}{2}+1)+t$^$\dfrac{n}{2})$
加起来求均值即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 60
#define LL long long LL pw[]; int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
} int main()
{
int n,t;
while(scanf("%d%d",&n,&t)!=EOF)
{
pw[]=;
for(int i=;i<=n;i++) pw[i]=pw[i-]*t;
LL a=;
for(int i=;i<n;i++) a+=pw[gcd(i,n)];
LL b=;
if(n%==) b=n*pw[(n+)/];
else b=n/*(pw[n/+]+pw[n/]);
printf("%lld %lld\n",a/n,(a+b)//n);
}
return ;
}
其实觉得这题的数据范围过不了啊,不是10^50了么????
为什么大家都这样打??
2017-01-11 11:18:14
最新文章
- VB操作EXCEL文件
- 关于session和cookie
- Android adb命令 一
- Tableau:数据可视化之急速BI
- jQuery Mobile + HTML5
- ios9+xcode7 适配笔记
- hdoj 1262 寻找素数对
- draw9patch超详细教程
- Extending Robolectric
- [Redux] Extracting Container Components (FilterLink)
- ios监听ScrollView/TableView滚动的正确姿势
- 面向面试编程——javascript对象的几种创建方式
- SSE图像算法优化系列十:简单的一个肤色检测算法的SSE优化。
- CentOS7的一些初始化
- JQuery td内容获取,修改
- deepin 下安装goland中文字体显示全是方块
- mysql配置外部允许外部连接
- Android--UI之ScrollView
- 【XSY1762】染色问题 网络流
- Python中加入中文注释
热门文章
- POJ 2991 Crane (线段树)
- metlnfo 5.3.1 sql注入复现
- Python标准库笔记(2) — re模块
- Android ADT插件更新后程序运行时抛出java.lang.VerifyError异常解决办法
- Mybatis学习 PageHelper分页插件
- thinkphp5 消息队列thinkphp-queue扩展
- 阿里云ftp连接遇到的错误,entering passive mode失败(一个并不成熟的产品?)
- Linux下批量Kill多个进程的方法
- python_day7学习笔记
- [].forEach.call($$(";*";),function(a){ a.style.outline=";1px solid #";+(~~(Math.random()*(1<;<;24))).toString(16) })