數(shù)學(xué)類題目小結(jié)

    從放暑假前周sir給我講了一個(gè)用polya計(jì)數(shù)法和burnside定理做的題目（pku2409）后，突然覺(jué)得組合數(shù)學(xué)挺有意思，然后從那時(shí)起到現(xiàn)在幾乎都在做這類的題目。
做到現(xiàn)在感覺(jué)這類題目的一些基本知識(shí)點(diǎn)都差不多有所了解了，水題也刷了不少，但還有很多難題自己實(shí)在是做不動(dòng)，所以準(zhǔn)備把這類題目先放一放，然后把前段時(shí)間做的水題整理一下（供以后的初學(xué)者參考，大牛就不要看了哈，都是水題）。剩下的比較難的題目就慢慢來(lái)吧，以后做出來(lái)再不上，這個(gè)小結(jié)會(huì)不斷地更新。也希望大家有好的題目可以推薦一下，分享一下哈。

     感謝：周sir，J_factory和福州大學(xué)神牛aekdycoin，大連理工大學(xué)神牛czyuan。

不扯了，進(jìn)入主題：

    1.burnside定理，polya計(jì)數(shù)法
這個(gè)專題我單獨(dú)寫(xiě)了個(gè)小結(jié)，大家可以簡(jiǎn)單參考一下：polya 計(jì)數(shù)法，burnside定理小結(jié)

    2.置換，置換的運(yùn)算
    置換的概念還是比較好理解的，《組合數(shù)學(xué)》里面有講。對(duì)于置換的冪運(yùn)算大家可以參考一下潘震皓的那篇《置換群快速冪運(yùn)算研究與探討》，寫(xiě)的很好。
*簡(jiǎn)單題：（應(yīng)該理解概念就可以了）
pku3270 Cow Sorting
http://acm.pku.edu.cn/JudgeOnline/problem?id=3270
    pku1026 Cipher
http://acm.pku.edu.cn/JudgeOnline/problem?id=1026
    *置換冪運(yùn)算：
pku1721 CARDS
http://162.105.81.212/JudgeOnline/problem?id=1721
    pku3128 Leonardo's Notebook
http://162.105.81.212/JudgeOnline/problem?id=3128
    *推薦：（不錯(cuò)的應(yīng)用）
pku3590 The shuffle Problem
http://162.105.81.212/JudgeOnline/problem?id=3590

    3.素?cái)?shù)，整數(shù)分解，歐拉函數(shù)
素?cái)?shù)是可能數(shù)論里最永恒，最經(jīng)典的問(wèn)題了（我們的隊(duì)名就叫PrimeMusic^-^）。素?cái)?shù)的判斷，篩法求素?cái)?shù)，大素?cái)?shù)的判斷···還有很多其他問(wèn)題都會(huì)用到素?cái)?shù)。
*最水最水的：（心情不爽時(shí)用來(lái)解悶吧）
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（很好的一個(gè)應(yīng)用）
http://162.105.81.212/JudgeOnline/problem?id=2689
    *反素?cái)?shù)：
zoj2562 More Divisors
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562
    *素?cái)?shù)判斷，整數(shù)分解：
這兩題都要用到miller_rabin的素?cái)?shù)判斷和pollard_rho的整數(shù)分解，算法書(shū)上都會(huì)有，應(yīng)該是屬于模板題吧，不過(guò)最好看懂自己敲一遍。
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
    *歐拉函數(shù)：
數(shù)論里很多地方都能用到歐拉函數(shù)，很重要的。
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 （快速求歐拉函數(shù)）
http://162.105.81.212/JudgeOnline/problem?id=2478
    pku3090 Visible Lattice Points （法雷級(jí)數(shù)）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3090
    *推薦：（歐拉函數(shù)，費(fèi)馬小定理）
pku3358 Period of an Infinite Binary Expansion
http://acm.pku.edu.cn/JudgeOnline/problem?id=3358
    *整數(shù)分解
這個(gè)也很重要的耶，包括大數(shù)的表示方法。
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 （分?jǐn)?shù)的最小公倍數(shù)）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3101

    4.擴(kuò)展歐幾里得，線性同余，中國(guó)剩余定理
    這應(yīng)該是數(shù)論里比較重要的一個(gè)部分吧，這類的題目也挺多，具體的內(nèi)容最好先看看數(shù)論書(shū)，我也整理過(guò)一些，可以參考參考：
http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html
    *簡(jiǎn)單題：
pku1006 Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
    pku1061 青蛙的約會(huì)
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
    *強(qiáng)烈推薦：
sgu106 The equation
http://acm.sgu.ru/problem.php?contest=0&problem=106
    pku3708 Recurrent Function （經(jīng)典）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3708

    5.約瑟夫環(huán)問(wèn)題
這個(gè)問(wèn)題還是比較有意思的，不是很難。
*簡(jiǎn)單題：
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.高斯消元法解方程
其實(shí)解方程并不是很難，就是按線性代數(shù)中學(xué)的那種方法，把系數(shù)矩陣化成上三角矩陣或數(shù)量矩陣，不過(guò)有些題目要判斷是否有解，或枚舉所有解。不過(guò)這類題目我認(rèn)為比較難的還是怎么去建立這個(gè)方程組，這個(gè)理解了，就沒(méi)什么大問(wèn)題了。
*簡(jiǎn)單題：
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 開(kāi)關(guān)問(wèn)題
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
    *強(qiáng)烈推薦：
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
    *變態(tài)題：
pku1487 Single-Player Games
http://162.105.81.212/JudgeOnline/problem?id=1487  

7.矩陣
用矩陣來(lái)解決問(wèn)題確實(shí)很常見(jiàn)，但我現(xiàn)在用到還不是很好，很多難題我還不會(huì)做。建議大家可以去看Matrix67的那篇關(guān)于矩陣的十個(gè)問(wèn)題，確實(shí)很經(jīng)典，但不太好看懂。
*簡(jiǎn)單：
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.高次同余方程
有關(guān)這個(gè)問(wèn)題我應(yīng)該是沒(méi)什么發(fā)言權(quán)了，A^B%C=D，我現(xiàn)在只會(huì)求D和B，唉，很想知道A該怎么求。就先推薦幾道題目吧，這里涉及到了一個(gè)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.容斥原理，鴿巢原理
    很有用的兩個(gè)定理，但好像單獨(dú)考這兩個(gè)定理的不是很多。
*鴿巢原理：
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.找規(guī)律，推公式
這類題目的設(shè)計(jì)一般都非常巧妙，真的是很難想出來(lái)，但只要找到規(guī)律或推出公式，就不是很難了。我很多都是在參考別人思路的情況下做的，能自己想出來(lái)真的很不容易。
*個(gè)人感覺(jué)都挺不錯(cuò)的：
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.排列組合，區(qū)間計(jì)數(shù)，計(jì)數(shù)序列
這些題目可能需要一些組合數(shù)學(xué)知識(shí)，基本上高中的知識(shí)就夠了。區(qū)間計(jì)數(shù)問(wèn)題一般不難，但寫(xiě)的時(shí)候需要仔細(xì)一些，各種情況要考慮到位。至于像卡特蘭數(shù)，差分序列，斯特靈數(shù)···都還挺有意思，可以去看看《組合數(shù)學(xué)》。
*簡(jiǎn)單題：
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
    *計(jì)數(shù)序列：
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.二分法
二分的思想還是很重要的，這里就簡(jiǎn)單推薦幾個(gè)純粹的二分題。
*簡(jiǎn)單：
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.穩(wěn)定婚姻問(wèn)題
    無(wú)意中接觸到這個(gè)算法，還蠻有意思的，《組合數(shù)學(xué)》中有詳細(xì)的介紹。
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.數(shù)位類統(tǒng)計(jì)問(wèn)題
    在航點(diǎn)月賽中第一次接觸到這類問(wèn)題，scau大牛little龍推薦我看了一篇論文，09年劉聰?shù)摹稖\談數(shù)位類統(tǒng)計(jì)問(wèn)題》，這篇論文相當(dāng)精彩，也相當(dāng)詳細(xì)，每道題都有詳細(xì)的分析和作者的參考代碼。所以我也沒(méi)什么可說(shuō)的了，這些題的代碼我博客里也就不貼了，大家直接去看論文吧。
簡(jiǎn)單：
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

      以上分類的題目在我的博客里都可以找到詳細(xì)的解題報(bào)告和參考代碼，由于比較麻煩就沒(méi)加鏈接，需要的可以用我的站內(nèi)搜索找到。

     本小結(jié)會(huì)不斷更新，轉(zhuǎn)載請(qǐng)注明出處。

     嚴(yán)重聲明：本文只適合ACM初學(xué)者，路過(guò)的大牛如有相同類型的比較好的題目可以推薦一些啊。