POJ2409 Let it Bead(Polya定理)
2018-07-12 07:32:37来源:博客园 阅读 ()
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6443 | Accepted: 4315 |
Description
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.
Input
Output
Sample Input
1 1 2 1 2 2 5 1 2 5 2 6 6 2 0 0
Sample Output
1 2 3 5 8 13 21
Source
感觉这玩意儿认真的好神奇啊qwq。
为什么网上都是直接说循环节的大小但是不做说明qwq、、
算了还是背结论吧
若是直接旋转,那么有$n$中置换,第$i$种循环节数为$gcd(n, i)$
如果是对称
对于奇数来说,可以固定一个点,让其他点交换。共有$n$个点,每种循环节为$\frac{n + 1}{2}$
对于偶数来说,有两种对称方式,
一种是以中线为中心,两边对称,共有$N / 2$种方式,每种循环节为$\frac{n + 2}{2}$
另一种是两个点的连线为中心,两边对称,共有$N/ 2$种方式,每种循环节为$\frac{n}{2}$
然后直接上polya定理就行了
POJ的评测机也是没谁了
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #define LL long long const int MAXN = 1e5 + 10; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int C, N; int fastpow(int a, int p) { int base = 1; while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } main() { while(scanf("%d %d", &C, &N)) { if(C == 0 && N == 0) break; int ans = 0; for(int i = 1; i <= N; i++) ans += fastpow(C, __gcd(i, N)); if(N & 1) ans = ans + N * fastpow(C, (N + 1) / 2); else ans = ans + N / 2 * (fastpow(C, (N + 2) / 2) + fastpow(C, N / 2)); printf("%d\n", ans / 2 / N); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 中的new和delete理解与实操应用 2020-03-19
- 【做题笔记】P2871 [USACO07DEC]手链Charm Bracelet 2020-02-14
- C++的new&delete 2020-02-10
- C++的new和delete 2019-12-25
- c++-构造函数练习和delete,new 2019-12-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash