POJ2154 Color(Polya定理)
2018-07-11 03:30:41来源:博客园 阅读 ()
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 11654 | Accepted: 3756 |
Description
You only need to output the answer module a given number P.
Input
Output
Sample Input
5 1 30000 2 30000 3 30000 4 30000 5 30000
Sample Output
1 3 11 70 629
Source
Polya定理:
假设$G$是$p$个对象的一个置换群,用$m$种颜色涂染$p$个对象,则不同颜色的方案数为
$L = \frac{1}{|G|}\sum_{g_i \in G}m^{c(g_i)}$
$G = \{g_1, g_2, \dots g_s \}$,$c(g_i)$为置换$g_i$的循环节数
本题而言第$i$种置换的循环节数为$gcd(n, i)$
因此答案为$L = \frac{1}{n}\sum_{i = 1}^n n^{gcd(i, n}$
枚举约数,用欧拉函数计算,时间复杂度$O(T\sqrt(N) f(n))$,$f(n)$表示小于$\sqrt(n)$的质因子的个数
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #define LL long long const int MAXN = 1e5 + 10; 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 T, N, mod; int fastpow(int a, int p, int mod) { int base = 1; a %= mod; while(p) { if(p & 1) base = (base * a) % mod; a = (a * a) % mod; p >>= 1; } return base % mod; } int prime[MAXN], tot, vis[MAXN]; void Prime() { for(int i = 2; i <= MAXN - 10; i++) { if(!vis[i]) prime[++tot] = i; for(int j = 1; j <= tot && prime[j] * i <= MAXN - 10; j++) { vis[i * prime[j]] = 1; if(!i % prime[j]) break; } } } int phi(int x, int mod) { int limit , ans = x; for(int i = 1; i <= tot && prime[i] * prime[i] <= x; i++) { if(!(x % prime[i])) { ans = ans - ans / prime[i]; while((x % prime[i]) == 0) x /= prime[i]; } } if(x > 1) ans = ans - ans / x; // printf("%d", ans % mod); return ans % mod; } main() { T = read(); Prime(); while(T--) { N = read(); mod = read(); int ans = 0, now = N; for(int d = 1; d * d<= N; d++) { if(d * d == N) ans = (ans + fastpow(N, d - 1, mod) % mod * phi(N / d, mod) % mod) % mod; else if( (N % d) == 0) { ans = (ans + fastpow(N, d - 1, mod) * phi(N / d, mod) + fastpow(N, N / d - 1, mod) * phi(d, mod)) % mod; } //printf("%d\n", ans); } //if(now > 0) ans += fastpow(N, now - 1, mod) * phi(N / now, mod); printf("%d\n", ans % mod); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CF1178 F1 Short Colorful Strip 2019-08-16
- [AtCoder][ARC081]Coloring Dominoes 题解 2018-07-28
- POJ1286 Necklace of Beads(Polya定理) 2018-07-12
- POJ2409 Let it Bead(Polya定理) 2018-07-12
- c# 把 颜色值Hex 转换为 Color 2018-06-18
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