『轉』數學專輯

1.burnside定理，polya計數法

這個大家可以看brudildi的《組合數學》，那本書的這一章寫的很詳細也很容易了解。最好能完全看懂了，了解了再去做題，不要隻記個公式。

*簡單題：（直接用套公式就可以了）

pku2409 let it bead  

http://acm.pku.edu.cn/judgeonline/problem?id=2409

pku2154 color

http://acm.pku.edu.cn/judgeonline/problem?id=2154

pku1286 necklace of beads

http://acm.pku.edu.cn/judgeonline/problem?id=1286

*強烈推薦：（這題很不錯哦，很巧妙）

pku2888 magic bracelet

http://162.105.81.212/judgeonline/problem?id=2888

2.置換，置換的運算

置換的概念還是比較好了解的，《組合數學》裡面有講。對于置換的幂運算大家可以參考一下潘震皓的那篇《置換群快速幂運算研究與探讨》，寫的很好。

*簡單題：（應該了解概念就可以了）

pku3270 cow sorting

http://acm.pku.edu.cn/judgeonline/problem?id=3270

pku1026 cipher

http://acm.pku.edu.cn/judgeonline/problem?id=1026

*置換幂運算：

pku1721 cards

http://162.105.81.212/judgeonline/problem?id=1721

pku3128 leonardo‘s notebook

http://162.105.81.212/judgeonline/problem?id=3128

*推薦：（不錯的應用）

pku3590 the shuffle problem

http://162.105.81.212/judgeonline/problem?id=3590

3.素數，整數分解，歐拉函數

素數是可能數論裡最永恒，最經典的問題了（我們的隊名就叫primemusic^-^）。素數的判斷，篩法求素數，大素數的判斷···還有很多其他問題都會用到素數。

*最水最水的：（心情不爽時用來解悶吧）

pku1365 prime land

pku2034 anti-prime sequences

pku2739 sum of consecutive prime numbers

pku3518 prime gap

pku3126 prime path

pku1595 prime cuts

pku3641 pseudoprime numbers

pku2191 mersenne composite numbers

pku1730 perfect pth powers

pku2262 goldbach‘s conjecture

pku2909 goldbach‘s conjecture

*篩法：

pku2689 prime distance（很好的一個應用）

http://162.105.81.212/judgeonline/problem?id=2689

*反素數：

zoj2562 more divisors

http://acm.zju.edu.cn/onlinejudge/showproblem.do?problemcode=2562

*素數判斷，整數分解：

這兩題都要用到miller_rabin的素數判斷和pollard_rho的整數分解，算法書上都會有，應該是屬于模闆題吧，不過最好看懂自己敲一遍。

pku1811 prime test

http://acm.pku.edu.cn/judgeonline/problem?id=1811

pku2429 gcd & lcm inverse

http://acm.pku.edu.cn/judgeonline/problem?id=2429

*歐拉函數：

數論裡很多地方都能用到歐拉函數，很重要的。

pku1284 primitive roots （很水）

http://acm.pku.edu.cn/judgeonline/problem?id=1284

pku2407 relatives （很水）

http://acm.pku.edu.cn/judgeonline/problem?id=2407

pku2773 happy 2006

http://162.105.81.212/judgeonline/problem?id=2773

pku2478 farey sequence （快速求歐拉函數）

http://162.105.81.212/judgeonline/problem?id=2478

pku3090 visible lattice points （法雷級數）

http://acm.pku.edu.cn/judgeonline/problem?id=3090

*推薦：（歐拉函數，費馬小定理）

pku3358 period of an infinite binary expansion

http://acm.pku.edu.cn/judgeonline/problem?id=3358

*整數分解

這個也很重要的耶，包括大數的表示方法。

pku2992 divisors

http://acm.pku.edu.cn/judgeonline/problem?id=2992

fzu1753 another easy problem

http://acm.fzu.edu.cn/problem.php?pid=1753

hit2813 garden visiting

http://acm-hit.sunner.cn/judge/show.php?proid=2813

pku3101 astronomy （分數的最小公倍數）

http://acm.pku.edu.cn/judgeonline/problem?id=3101

4.擴充歐幾裡得，線性同餘，中國剩餘定理

這應該是數論裡比較重要的一個部分吧，這類的題目也挺多，具體的内容最好先看看數論書，我也整理過一些，可以參考參考：

   http://hi.baidu.com/%b1%bf%d0%a1%ba%a2%5fshw/blog/item/0676025d56a87d4afbf2c093.html

*簡單題：

pku1006 biorhythms

http://acm.pku.edu.cn/judgeonline/problem?id=1006

pku1061 青蛙的約會

http://acm.pku.edu.cn/judgeonline/problem?id=1061

pku2891 strange way to express integers

http://acm.pku.edu.cn/judgeonline/problem?id=2891

pku2115 c looooops

http://acm.pku.edu.cn/judgeonline/problem?id=2115

pku2142 the balance

http://162.105.81.212/judgeonline/problem?id=2142

*強烈推薦：

sgu106 the equation

http://acm.sgu.ru/problem.php?contest=0&problem=106

pku3708 recurrent function （經典）

http://acm.pku.edu.cn/judgeonline/problem?id=3708

5.約瑟夫環問題

這個問題還是比較有意思的，不是很難。

pku3517 and then there was one

http://acm.pku.edu.cn/judgeonline/problem?id=3517

pku1781 in danger

http://acm.pku.edu.cn/judgeonline/problem?id=1781

pku1012 joseph

http://162.105.81.212/judgeonline/problem?id=1012

pku2244 eeny meeny moo

http://162.105.81.212/judgeonline/problem?id=2244

*推薦：

pku2886 who gets the most candies?

http://162.105.81.212/judgeonline/problem?id=2886

6.高斯消元法解方程

其實解方程并不是很難，就是按線性代數中學的那種方法，把系數矩陣化成上三角矩陣或數量矩陣，不過有些題目要判斷是否有解，或枚舉所有解。不過這類題目我認為比較難的還是怎麼去建立這個方程組，這個了解了，就沒什麼大問題了。

pku1222 extended lights out

http://162.105.81.212/judgeonline/problem?id=1222

pku1681 painter‘s problem

http://162.105.81.212/judgeonline/problem?id=1681

pku1830 開關問題

http://162.105.81.212/judgeonline/problem?id=1830

pku2947 widget factory

http://162.105.81.212/judgeonline/problem?id=2947

pku2065 seti

http://162.105.81.212/judgeonline/problem?id=2065

pku1753 flip game

http://162.105.81.212/judgeonline/problem?id=1753

pku3185 the water bowls

http://162.105.81.212/judgeonline/problem?id=3185

*變态題：

pku1487 single-player games

http://162.105.81.212/judgeonline/problem?id=1487   

7.矩陣

用矩陣來解決問題确實很常見，但我現在用到還不是很好，很多難題我還不會做。建議大家可以去看matrix67的那篇關于矩陣的十個問題，确實很經典，但不太好看懂。

*簡單：

pku3070 fibonacci

http://162.105.81.212/judgeonline/problem?id=3070

pku3233 matrix power series

http://162.105.81.212/judgeonline/problem?id=3233

pku3735 training little cats

http://162.105.81.212/judgeonline/problem?id=3735

8.高次同餘方程

有關這個問題我應該是沒什麼發言權了，a^b%c=d，我現在隻會求d和b，唉，很想知道a該怎麼求。就先推薦幾道題目吧，這裡涉及到了一個baby-step，giant-step算法。

fzu1759 super a^b mod c

http://acm.fzu.edu.cn/problem.php?pid=1759

pku3243 clever y

http://162.105.81.212/judgeonline/problem?id=3243

pku2417 discrete logging

http://162.105.81.212/judgeonline/problem?id=2417

hdu2815 mod tree

http://acm.hdu.edu.cn/showproblem.php?pid=2815

9.容斥原理，鴿巢原理

很有用的兩個定理，但好像單獨考這兩個定理的不是很多。

*鴿巢原理：

pku2365 find a multiple

http://162.105.81.212/judgeonline/problem?id=2356

pku3370 halloween treats

http://162.105.81.212/judgeonline/problem?id=3370

*容斥原理：

hdu1695 gcd

http://acm.hdu.edu.cn/showproblem.php?pid=1695

hdu2461 rectangles

http://acm.hdu.edu.cn/showproblem.php?pid=2461

10.找規律，推公式

這類題目的設計一般都非常巧妙，真的是很難想出來，但隻要找到規律或推出公式，就不是很難了。我很多都是在參考别人思路的情況下做的，能自己想出來真的很不容易。

*個人感覺都挺不錯的：

pku3372 candy distribution

http://162.105.81.212/judgeonline/problem?id=3372

pku3244 difference between triplets

http://162.105.81.212/judgeonline/problem?id=3244

pku1809 regetni

http://162.105.81.212/judgeonline/problem?id=1809

pku1831 不定方程組

http://162.105.81.212/judgeonline/problem?id=1831

pku1737 connected graph

http://162.105.81.212/judgeonline/problem?id=1737

pku2480 longge‘s problem

http://162.105.81.212/judgeonline/problem?id=2480

pku1792 hexagonal routes

http://acm.pku.edu.cn/judgeonline/problem?id=1792

11.排列組合，區間計數，計數序列

這些題目可能需要一些組合數學知識，基本上高中的知識就夠了。區間計數問題一般不難，但寫的時候需要仔細一些，各種情況要考慮到位。至于像卡特蘭數，差分序列，斯特靈數···都還挺有意思，可以去看看《組合數學》。

pku1850 code

http://162.105.81.212/judgeonline/problem?id=1850

pku1150 the last non-zero digit

http://162.105.81.212/judgeonline/problem?id=1150

pku1715 hexadecimal numbers

http://162.105.81.212/judgeonline/problem?id=1715

pku2282 the counting problem

http://162.105.81.212/judgeonline/problem?id=2282

pku3286 how many 0‘s?

http://162.105.81.212/judgeonline/problem?id=3286

pku3252 round numbers

http://162.105.81.212/judgeonline/problem?id=3252

*計數序列：

pku1430 binary stirling numbers

http://162.105.81.212/judgeonline/problem?id=1430

pku2515 birthday cake

http://acm.pku.edu.cn/judgeonline/problem?id=2515

pku1707 sum of powers

http://acm.pku.edu.cn/judgeonline/problem?id=1707

12.二分法

二分的思想還是很重要的，這裡就簡單推薦幾個純粹的二分題。

pku3273 monthly expense

http://162.105.81.212/judgeonline/problem?id=3273

pku3258 river hopscotch

http://162.105.81.212/judgeonline/problem?id=3258

pku1905 expanding rods

http://162.105.81.212/judgeonline/problem?id=1905

pku3122 pie

http://162.105.81.212/judgeonline/problem?id=3122

pku1845 sumdiv

http://acm.pku.edu.cn/judgeonline/problem?id=1845

13.穩定婚姻問題

無意中接觸到這個算法，還蠻有意思的，《組合數學》中有詳細的介紹。

pku3487 the stable marriage problem

http://acm.pku.edu.cn/judgeonline/problem?id=3487

zoj1576 marriage is stable

http://acm.zju.edu.cn/onlinejudge/showproblem.do?problemcode=1576

14.數位類統計問題

在航點月賽中第一次接觸到這類問題，scau大牛little龍推薦我看了一篇論文，09年劉聰的《淺談數位類統計問題》，這篇論文相當精彩，也相當詳 細，每道題都有詳細的分析和作者的參考代碼。是以我也沒什麼可說的了，這些題的代碼我部落格裡也就不貼了，大家直接去看論文吧。

簡單：

ural1057 amount of degrees

http://acm.timus.ru/problem.aspx?space=1&num=1057

spoj1182 sorted bit squence

https://www.spoj.pl/problems/sortbit/

hdu3271 snibb

http://acm.hdu.edu.cn/showproblem.php?pid=3271

較難：

spoj2319 sequence

https://www.spoj.pl/problems/bigseq/

sgu390 tickets

http://acm.sgu.ru/problem.php?contest=0&problem=390

以上分類的題目在我的部落格裡都可以找到詳細的解題報告和參考代碼，由于比較麻煩就沒加連結，需要的可以用我的站内搜尋找到。

本小結會不斷更新，轉載請注明出處。