1.題目相關(guān)
-
標簽：
Polya - 題目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1004
- 題目大意：中文題。
2.思路
- 比較基礎(chǔ)的Polya計數(shù)。
- 利用Burnside引理+K背包+乘法逆元。
居然不經(jīng)意間就會了K背包 - 前面兩個網(wǎng)上書上資料很多，重點講乘法逆元。
- 先講一下擴展歐幾里得。
設(shè)
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;
}
- 有了以上的知識就可以來討論有關(guān) (a/b) % p 的值的問題了
- 先來看定義：
- 滿足 a·k ≡ 1 (mod p) 的 k 值就是 a 關(guān)于 p 的乘法逆元。
- 為什么要用乘法逆元呢？
- 當我們要求 (a/b) % p 的值，且 a 很大，無法直接求得 a/b 的值時，我們就要用到乘法逆元。
- 我們可以通過求 b 關(guān)于 p 的乘法逆元 k，將 a 乘上 k 再模 p，即 (a·k) % p。其結(jié)果與 (a/b) mod p 等價。
- 證明如下
根據(jù)
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 的值只要調(diào)用一下 exgcd 就好了。但需注意接出來 k 可能是負數(shù)，所以要不斷加 p 。
- 代碼如下
exgcd(b, p, k, y);
while (k <= 0) k += p;
-
注意題目中有一個比較
坑爹的一個地方：沒有(1,2,3...n-1,n)這個置換。其實還是我太菜
