1.题目相关
-
标签：
Polya - 题目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1004
- 题目大意：中文题。
2.思路
- 比较基础的Polya计数。
- 利用Burnside引理+K背包+乘法逆元。
居然不经意间就会了K背包 - 前面两个网上书上资料很多，重点讲乘法逆元。
- 先讲一下扩展欧几里得。
设
a·X1 + b·Y1 = gcd(a, b)b·X2 + (a % b)·Y2 = gcd(b, a % b)
其中
gcd(a, b) = gcd(b, a % b)a % b = a-(a/b)·b
整理可得
a·X1 + b·Y1 = b·X2 + (a-(a/b)·b)·Y2
a·X1 + b·Y1 = a·Y2 + b·[X2-(a/b)]·Y2
所以
X1 = Y2 , Y1 = X2-(a/b)·Y2
- 代码如下
void exgcd(int a, int b, int &x, int &y) {
if (b == 0) {x = 1; y = 0; return;}
exgcd(b, a%b, x, y);
int t = x; x = y; y = t-a/b*y;
}
- 有了以上的知识就可以来讨论有关 (a/b) % p 的值的问题了
- 先来看定义：
- 满足 a·k ≡ 1 (mod p) 的 k 值就是 a 关于 p 的乘法逆元。
- 为什么要用乘法逆元呢？
- 当我们要求 (a/b) % p 的值，且 a 很大，无法直接求得 a/b 的值时，我们就要用到乘法逆元。
- 我们可以通过求 b 关于 p 的乘法逆元 k，将 a 乘上 k 再模 p，即 (a·k) % p。其结果与 (a/b) mod p 等价。
- 证明如下
根据
b·k ≡ 1 (mod p)
可得
b·k = p·x + 1
k = (p·x + 1) / b
把 k 代入
(a·k) mod p
得原式
= (a·(p·x + 1) / b) % p
= ((a·p·x)/b + a/b) % p
= [((a·p·x)/b) % p + (a/b)] mod p
所以原式等于
(a/b) % p
- 而 k 的值只要调用一下 exgcd 就好了。但需注意接出来 k 可能是负数，所以要不断加 p 。
- 代码如下
exgcd(b, p, k, y);
while (k <= 0) k += p;
-
注意题目中有一个比较
坑爹的一个地方：没有(1,2,3...n-1,n)这个置换。其实还是我太菜
