从放暑假前周sir给我讲了一个用polya计数法和burnside定理做的题目（pku2409）后，突然觉得组合数学挺有意思，然后从那时起到现在几乎都在做这类的题目。  做到现在感觉这类题目的一些基本知识点都差不多有所了解了，水题也刷了不少，但还有很多难题自己实在是做不动，所以准备把这类题目先放一放，然后把前段时间做的水题整理一下（供以后的初学者参考，大牛就不要看了哈，都是水题）。剩下的比较难的题目就慢慢来吧，以后做出来再不上，这个小结会不断地更新。也希望大家有好的题目可以推荐一下，分享一下哈。       感谢：周sir，J_factory和福州大学神牛aekdycoin，大连理工大学神牛czyuan。  不扯了，进入主题：      1.burnside定理，polya计数法  这个专题我单独写了个小结，大家可以简单参考一下：polya 计数法，burnside定理小结      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        以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码，由于比较麻烦就没加链接，需要的可以用我的站内搜索找到。       本小结会不断更新，转载请注明出处。       严重声明：本文只适合ACM初学者，路过的大牛如有相同类型的比较好的题目可以推荐一些啊。  来自: http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/5305e12c7289973e359bf768.html