本文共 28914 字，大约阅读时间需要 96 分钟。
- 从放暑假前周sir给我讲了一个用polya计数法和burnside定理做的题目（pku2409）后，突然觉得组合数学挺有意思，然后从那时起到现在几乎都在做这类的题目。
- 做到现在感觉这类题目的一些基本知识点都差不多有所了解了，水题也刷了不少，但还有很多难题自己实在是做不动，所以准备把这类题目先放一放，然后把前段时间做的水题整理一下（供以后的初学者参考，大牛就不要看了哈，都是水题）。剩下的比较难的题目就慢慢来吧，以后做出来再不上，这个小结会不断地更新。也希望大家有好的题目可以推荐一下，分享一下哈。
- 感谢：周sir，J_factory和福州大学神牛aekdycoin，大连理工大学神牛czyuan。
- 不扯了，进入主题：
- 1.burnside定理，polya计数法
- 这个专题我单独写了个小结，大家可以简单参考一下：polya 计数法，burnside定理小结
- 2.置换，置换的运算
- 置换的概念还是比较好理解的，《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》，写的很好。
- *简单题：（应该理解概念就可以了）
- pku3270 Cow Sorting
- http:
- pku1026 Cipher
- http:
- *置换幂运算：
- pku1721 CARDS
- http:
- pku3128 Leonardo's Notebook
- http:
- *推荐：（不错的应用）
- pku3590 The shuffle Problem
- http:
- 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:
- *反素数：
- zoj2562 More Divisors
- http:
- *素数判断，整数分解：
- 这两题都要用到miller_rabin的素数判断和pollard_rho的整数分解，算法书上都会有，应该是属于模板题吧，不过最好看懂自己敲一遍。
- pku1811 Prime Test
- http:
- pku2429 GCD & LCM Inverse
- http:
- *欧拉函数：
- 数论里很多地方都能用到欧拉函数，很重要的。
- pku1284 Primitive Roots （很水）
- http:
- pku2407 Relatives （很水）
- http:
- pku2773 Happy 2006
- http:
- pku2478 Farey Sequence （快速求欧拉函数）
- http:
- pku3090 Visible Lattice Points （法雷级数）
- http:
- *推荐：（欧拉函数，费马小定理）
- pku3358 Period of an Infinite Binary Expansion
- http:
- *整数分解
- 这个也很重要的耶，包括大数的表示方法。
- pku2992 Divisors
- http:
- fzu1753 Another Easy Problem
- http:
- hit2813 Garden visiting
- http:
- pku3101 Astronomy （分数的最小公倍数）
- http:
- 4.扩展欧几里得，线性同余，中国剩余定理
- 这应该是数论里比较重要的一个部分吧，这类的题目也挺多，具体的内容最好先看看数论书，我也整理过一些，可以参考参考：
- http:
- *简单题：
- pku1006 Biorhythms
- http:
- pku1061 青蛙的约会
- http:
- pku2891 Strange Way to Express Integers
- http:
- pku2115 C Looooops
- http:
- pku2142 The Balance
- http:
- *强烈推荐：
- sgu106 The equation
- http:
- pku3708 Recurrent Function （经典）
- http:
- 5.约瑟夫环问题
- 这个问题还是比较有意思的，不是很难。
- *简单题：
- pku3517 And Then There Was One
- http:
- pku1781 In Danger
- http:
- pku1012 Joseph
- http:
- pku2244 Eeny Meeny Moo
- http:
- *推荐：
- pku2886 Who Gets the Most Candies?
- http:
- 6.高斯消元法解方程
- 其实解方程并不是很难，就是按线性代数中学的那种方法，把系数矩阵化成上三角矩阵或数量矩阵，不过有些题目要判断是否有解，或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组，这个理解了，就没什么大问题了。
- *简单题：
- pku1222 EXTENDED LIGHTS OUT
- http:
- pku1681 Painter's Problem
- http:
- pku1830 开关问题
- http:
- *推荐：
- pku2947 Widget Factory
- http:
- pku2065 SETI
- http:
- *强烈推荐：
- pku1753 Flip Game
- http:
- pku3185 The Water Bowls
- http:
- *变态题：
- pku1487 Single-Player Games
- http:
- 7.矩阵
- 用矩阵来解决问题确实很常见，但我现在用到还不是很好，很多难题我还不会做。建议大家可以去看Matrix67的那篇关于矩阵的十个问题，确实很经典，但不太好看懂。
- *简单：
- pku3070 Fibonacci
- http:
- pku3233 Matrix Power Series
- http:
- pku3735 Training little cats
- http:
- 8.高次同余方程
- 有关这个问题我应该是没什么发言权了，A^B%C=D，我现在只会求D和B，唉，很想知道A该怎么求。就先推荐几道题目吧，这里涉及到了一个baby-step，giant-step算法。
- fzu1759 Super A^B mod C
- http:
- pku3243 Clever Y
- http:
- pku2417 Discrete Logging
- http:
- hdu2815 Mod Tree
- http:
- 9.容斥原理，鸽巢原理
- 很有用的两个定理，但好像单独考这两个定理的不是很多。
- *鸽巢原理：
- pku2365 Find a multiple
- http:
- pku3370 Halloween treats
- http:
- *容斥原理：
- hdu1695 GCD
- http:
- hdu2461 Rectangles
- http:
- 10.找规律，推公式
- 这类题目的设计一般都非常巧妙，真的是很难想出来，但只要找到规律或推出公式，就不是很难了。我很多都是在参考别人思路的情况下做的，能自己想出来真的很不容易。
- *个人感觉都挺不错的：
- pku3372 Candy Distribution
- http:
- pku3244 Difference between Triplets
- http:
- pku1809 Regetni
- http:
- pku1831 不定方程组
- http:
- pku1737 Connected Graph
- http:
- pku2480 Longge's problem
- http:
- pku1792 Hexagonal Routes
- http:
- 11.排列组合，区间计数，计数序列
- 这些题目可能需要一些组合数学知识，基本上高中的知识就够了。区间计数问题一般不难，但写的时候需要仔细一些，各种情况要考虑到位。至于像卡特兰数，差分序列，斯特灵数···都还挺有意思，可以去看看《组合数学》。
- *简单题：
- pku1850 Code
- http:
- pku1150 The Last Non-zero Digit
- http:
- pku1715 Hexadecimal Numbers
- http:
- pku2282 The Counting Problem
- http:
- pku3286 How many 0's?
- http:
- *推荐：
- pku3252 Round Numbers
- http:
- *计数序列：
- pku1430 Binary Stirling Numbers
- http:
- pku2515 Birthday Cake
- http:
- pku1707 Sum of powers
- http:
- 12.二分法
- 二分的思想还是很重要的，这里就简单推荐几个纯粹的二分题。
- *简单：
- pku3273 Monthly Expense
- http:
- pku3258 River Hopscotch
- http:
- pku1905 Expanding Rods
- http:
- pku3122 Pie
- http:
- *推荐：
- pku1845 Sumdiv
- http:
- 13.稳定婚姻问题
- 无意中接触到这个算法，还蛮有意思的，《组合数学》中有详细的介绍。
- pku3487 The Stable Marriage Problem
- http:
- zoj1576 Marriage is Stable
- http:
- 14.数位类统计问题
- 在航点月赛中第一次接触到这类问题，scau大牛little龙推荐我看了一篇论文，09年刘聪的《浅谈数位类统计问题》，这篇论文相当精彩，也相当详细，每道题都有详细的分析和作者的参考代码。所以我也没什么可说的了，这些题的代码我博客里也就不贴了，大家直接去看论文吧。
- 简单：
- ural1057 Amount of degrees
- http:
- spoj1182 Sorted bit squence
- https:
- hdu3271 SNIBB
- http:
- 较难：
- spoj2319 Sequence
- https:
- sgu390 Tickets
- http:
- 以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码，由于比较麻烦就没加链接，需要的可以用我的站内搜索找到。
- 本小结会不断更新，转载请注明出处。
- 严重声明：本文只适合ACM初学者，路过的大牛如有相同类型的比较好的题目可以推荐一些啊。
- 来自: http:
·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150
- 对数学类题目小结中的题目的简单解题报告：
- 偶然在网上看到某牛人发的数学题目小结，于是拷了回来做，下面每道题目后面注释的是我写的简单解题报告（有些只是注意事项），而且并非所有都有做，所以希望大家理解，目前正在更新中。
- 原文连接在这里：http:
- 这里题目之前有‘ ＃’ 的表示已过，‘ ？’ 表示做了但还没过。
-
- 1.burnside 定理，polya 计数法
- 这个大家可以看brudildi 的《组合数学》，那本书的这一章写的很详细也很容易理解。最好能完全看懂了，理解了再去做题，不要只记个公式。
- * 简单题：（直接用套公式就可以了）
- # pku2409 Let it Bead // 翻转时注意珠子为奇偶的情况。
- http:
- # pku2154 Color//LTC 的题目，看《具体数学》p141 ，有个化简的公式。
- http:
- # pku1286 Necklace of Beads // 和2409 一样
- http:
- * 强烈推荐：（这题很不错哦，很巧妙）
- # pku2888 Magic Bracelet // 见月赛解题报告.A[i][j] 为可达矩阵. 而且注意约数的个数范围。其中矩阵的幂可以预先求出所有matrix[2^i] 出来，然后根据二进制来 求。
- http:
- 2. 置换，置换的运算
- 置换的概念还是比较好理解的，《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》，写的很好。
- * 简单题：（应该理解概念就可以了）
- # pku3270 Cow Sorting // 列出置换，然后对于每一个置换循环，不断用环中的最小的那个和其他的进行换位，可以得到最优。另外还有一种情况就是用整个置换最小的那个和该环进行换位，对于每个环求出这两个的最小值加起来就可以了。
- http:
- # pku1026 Cipher // 先找出所有置换循环，然后对于每一位来计算k% 循环长度后对应于哪个位置,O(n) 复杂度。注意读写方面的东西。
- http:
- * 置换幂运算：
- # pku1721 CARDS // 详细见05 集训队论文《置换群快速幂运算研究与探讨》。
- http:
- # pku3128 Leonardo's Notebook// 摘自：http://blog.csdn.net/J_Factory/archive/2008/08/28 /2845330.aspx
- 题目意思是：一个置换是否可以由另一个置换的平方得来的。一个置换的平方，原来偶数长的循环会被分裂成两段长度相等的循环，而奇数长的循环不会被分裂。题目只是问是否存在，所以只要看所给置换中偶数长的循环是否成对，否则就不能由一个置换的平方得来。
- 补充：因为如果所给置换的循环是偶数，则肯定是由分裂过来的，那么一定是成对的，否则如果是奇数，那么有可能是原来是奇数，也有可能是原来的偶数分裂成两个奇数循环。
- http:
- * 推荐：（不错的应用）
- # pku3590 The shuffle Problem // 把n 分解成若干个数，使得他们的lcm 最大。在所取的数都是素数幂的时候是最大的，所以可以用递归来枚举所有的分解情况，而且由于要输出序最小的，所以对于剩下的数可以直接单独都作为一个循环，这样就可以使得序最小了。此外，这道题目需要注意求最大的lcm 的时候不能用dp 来做，因为这个具有后效 性，局部最优不一定使得全局最优。
- http:
- 3. 素数，整数分解，欧拉函数
- 素数是可能数论里最永恒，最经典的问题了（我们的队名就叫PrimeMusic^-^ ）。素数的判断，筛法求素数，大素数的判断··· 还有很多其他问题都会用到素数。
- * 最水最水的：（心情不爽时用来解闷吧）
- # pku1365 Prime Land
- # pku2034 Anti-prime Sequences// 直接搜索，用DL 优化会快很多。
- # 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 （很好的一个应用）// 先找出sqrt(2^32) 内的所有素数，然后类似筛选法筛选掉[l,u] 范围内的数
- http:
- * 反素数：
- # zoj2562 More Divisors //waing... 后记：素数表少打了一个19 ～晕死啊～。。
- http:
- * 素数判断，整数分解：
- 这两题都要用到miller_rabin 的素数判断和pollard_rho 的整数分解，算法书上都会有，应该是属于模板题吧，不过最好看懂自己敲一 遍。
- # pku1811 Prime Test // 学习miller 和pollard 的题目。
- http:
- # pku2429 GCD & LCM Inverse // 分解lcm/gcd 为互质的p,q ，要用到Miller Rabin 和Pollard rho 算法，基本上做出来之后都是模板题了。
- http:
- * 欧拉函数：
- 数论里很多地方都能用到欧拉函数，很重要的。
- # pku1284 Primitive Roots （很水）// 定理：对于奇素数m, 原根个数为phi(phi(m)), 由于phi(m)=m-1, 所以为phi(m-1)
- http:
- # pku2407 Relatives （很水）
- http:
- # pku2773 Happy 2006 //n 之后的互质的数都是n 之前的加上n 的倍数的。
- http:
- # pku2478 Farey Sequence （快速求欧拉函数）// 求前n 个欧拉函数的和，用学习指导里面的n*(1+lnln(n)) 的算法就可以了，非常快。
- http:
- # pku3090 Visible Lattice Points （法雷级数）
- http:
- * 推荐：（欧拉函数，费马小定理）
- # pku3358 Period of an Infinite Binary Expansion// 转化为高次同余方程。
- http:
- * 整数分解
- 这个也很重要的耶，包括大数的表示方法。
- # pku2992 Divisors// 注意预处理，有很多组数据.
- http:
- ? fzu1753 Another Easy Problem
- http:
- hit2813 Garden visiting
- http:
- ? pku3101 Astronomy （分数的最小公倍数）
- http:
- 4. 扩展欧几里得，线性同余，中国剩余定理
- 这应该是数论里比较重要的一个部分吧，这类的题目也挺多，具体的内容最好先看看数论书，我也整理过一些，可以参考参考：
- http:
- * 简单题：
- # pku1006 Biorhythms // 注意最后结果为0 或负数的情况
- http:
- # pku1061 青蛙的约会
- http:
- # pku2891 Strange Way to Express Integers //x==a1(mod m1),x==a2(mod m2), 两个方程可以求出x ，然后重新令a1 为求出的解x,m1=lcm(m1,m2) ，然后继续和后面的进行求解。注意数据运算过程中可能溢出的问题。
- http:
- # pku2115 C Looooops
- http:
- # pku2142 The Balance // 枚举，x=x0+b/d*t ，直到x>min(x+y)
- http:
- * 强烈推荐：
- # sgu106 The equation // 求ax+by=c 的时候，考虑a,b 为零的特殊情况，此外，若a,b 不是非负数，那么扩展欧几里德会有问题，于是我们可以把求x,y 变为求 x'=-x,y'=-y ，此时a,b, 就可以变为非负数来处理，同时x',y' 的范围也要相应取反。而且在取得区间时候，要注意区间边缘要进行相应的取 整。后记：要用cin,cout 才能AC ，用printf 会wa 。。。极度无奈中，偶然才发现的～_ ～!
- http:
- # pku3708 Recurrent Function （经典）// 具体数学第一章。对于每一位求出循环节m1 ，还有该位从m 达到k 最少要经过r1 次标号变化，于是就可以得到x==r1 (mod m1) ，然后同样的方法求其他的位，接着就可以两两方程这样解中国剩余定理。
- http:
- 5. 约瑟夫环问题
- 这个问题还是比较有意思的，不是很难。
- * 简单题：
- # pku3517 And Then There Was One
- http:
- # pku1781 In Danger
- http:
- # pku1012 Joseph // 考虑剩下k+1 个人，那么上一个出局的人肯定是坏人，所以考虑接下来一定要最后一个坏人出局，所以m==0 或1(mod k+1) 。然后枚举m ，再验证。
- http:
- # pku2244 Eeny Meeny Moo
- http:
- * 推荐：
- # pku2886 Who Gets the Most Candies?// 线段树+ 反素数。
- http:
- 6. 高斯消元法解方程
- 其实解方程并不是很难，就是按线性代数中学的那种方法，把系数矩阵化成上三角矩阵或数量矩阵，不过有些题目要判断是否有解，或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组，这个理解了，就没什么大问题了。
- * 简单题：
- # pku1222 EXTENDED LIGHTS OUT // 解异或运算的方程。n*m 个方程和未知数。
- http:
- # pku1681 Painter's Problem
- http:
- # pku1830 开关问题 // 以上三题做法都一样。
- http:
- * 推荐：
- # pku2947 Widget Factory // 最好要化成严格的阶梯型，方便判解。而且模某个数的时候解方程要用到扩展欧几里德算法。
- http:
- # pku2065 SETI// 与上题一样。
- http:
- * 强烈推荐：
- # pku1753 Flip Game // 数据范围比较小，枚举可过。如果用高斯消元做，那么对于多解的时候也是需要枚举的，而且这种类型不具有太大的扩展性，这里高斯消元不见的比枚举要优越。
- http:
- # pku3185 The Water Bowls // 同样如果对于无数解的时候，就需要对解进行枚举。其实这道题目可以先枚举第一位是否需要翻转，然后其他的就已经确定了，不过需要注意如果第一位翻转的时候，答案别忘了加上去，我因为这个搞了好久～～～郁闷。
- http:
-
- pku1395
- pku2055
- ural1561
- pku3254
- * 变态题：
- pku1487 Single-Player Games
- http:
- 7. 矩阵
- 用矩阵来解决问题确实很常见，但我现在用到还不是很好，很多难题我还不会做。建议大家可以去看Matrix67 的那篇关于矩阵的十个问题，确实很经典， 但不太好看懂。
- * 简单：
- pku3070 Fibonacci
- http:
- pku3233 Matrix Power Series
- http:
- pku3735 Training little cats
- http:
- 8. 高次同余方程
- 有关这个问题我应该是没什么发言权了，A^B%C=D ，我现在只会求D 和B ，唉，很想知道A 该怎么求。就先推荐几道题目吧，这里涉及到了一个baby- step ，giant-step 算法。
- # fzu1759 Super A^B mod C //a^b%c=a^(b%phi(c))%c , 注意a==c 的情况，
- http:
- # pku3243 Clever Y // 和上面差不多，不过c 不一定是素数，所以方法就是解出a^m*x+c*y=gcd(a^m,c) 的所有解来判断，若无解则不管，因为c 不是素数可能 a^m 没有逆。
- http:
- # pku2417 Discrete Logging //hash ，最直接的离散对数
- http:
- ？ hdu2815 Mod Tree
- http:
- # sgu261 求A wa test 23.. 后记：原来是hash 有错误，因为用了vector 后是从0 开始的，而我判断hash 链表结束的是0 ，如果恰好最后一个是在vector 的0 位 置，那么就会忽略掉这个数据，所以就会出现找不到那个数的情况。另外进行最后答案输出的时候，vector 的size （）是返回unsigned int 的，如果size( ）是0 ，那么size()-1 就是2^32-1 了，所以这里就需要特别注意。
- ? http:
- http:
- 9. 容斥原理，鸽巢原理
- 很有用的两个定理，但好像单独考这两个定理的不是很多。
- * 鸽巢原理：
- # pku2356 Find a multiple // 同下。
- http:
- # pku3370 Halloween treatsn 个数，寻找c 个(c<=n) ，使得他们的和为c 的倍数。由抽屉原理，前n 个数的 mod c 肯定有重复的，那么一定存在一个区间使得他们的和是c 的倍数。
- http:
- * 容斥原理：
- # hdu1695 GCD // 求gcd(x,y)=k 的个数，相当于求gcd(x/k,y/k)=1 的个数，其中x/k 在[a/k,b/k],y/k 在[c/k,d/k] 之间。所 以就是求在一定区间内，x ，y 互质的对数。假设b<d, （此处b,d 已除k ）那么对于<=b, 直接用欧拉函数就可以了，对于[b+1,d] 之 间的数，对于每一个分解质因数，然后利用容斥原理，求出［1,b ］之间和这个数互质的个数。注意最后答案可能超过int ，用I64d 输出。
- http:
- # hdu2461 Rectangles // 对称情况下才能使用懒标记，而且覆盖的标号不向下传。另外在pku3695 上同样的题目由于时限很紧，所以可以对坐标进行离散化。log1000 和 log40 还是有差别的。
- http:
- 10. 找规律，推公式
- 这类题目的设计一般都非常巧妙，真的是很难想出来，但只要找到规律或推出公式，就不是很难了。我很多都是在参考别人思路的情况下做的，能自己想出来真的很不容易。
- * 个人感觉都挺不错的：
- # pku3372 Candy Distribution// 找规律。。。其实可以进行分析的。
- http:
- # pku3244 Difference between Triplets// 这道题目要用到一个很巧妙的转化，把比较转化为绝对值的计算。因为max(a,b,c)-min(a,b,c)=(|a- b|+|a-c|+|b-c|)/2, 然后剩下的就容易做了。
- http:
- pku1809 Regetni
- http:
- pku1831 不定方程组
- http:
- # pku1737 Connected Graph //f[n] 为n 个点的联通数，那么f[n]=2^(c[n][2])-sigma(f[k]*c[i-1][k-1]*2^(c[n-k][2]))
- http:
- # pku2480 Longge's problem//sigma(gcd(i,n))=sigma(d|n && d*[gcd(i,n)==d]), 枚举所有n 的约数d ，然后对于n/d ，找出所有和n/d 互质的数的个数就是gcd(i,n)==d 的个数，从而用欧拉 函数解决。
- http:
- pku1792 Hexagonal Routes
- http:
- 11. 排列组合，区间计数，计数序列
- 这些题目可能需要一些组合数学知识，基本上高中的知识就够了。区间计数问题一般不难，但写的时候需要仔细一些，各种情况要考虑到位。至于像卡特兰数，差分序列，斯特灵数··· 都还挺有意思，可以去看看《组合数学》。
- * 简单题：
- pku1850 Code
- http:
- pku1150 The Last Non-zero Digit
- http:
- pku1715 Hexadecimal Numbers
- http:
- pku2282 The Counting Problem
- http:
- pku3286 How many 0's?
- http:
- * 推荐：
- pku3252 Round Numbers
- http:
- * 计数序列：
- pku1430 Binary Stirling Numbers
- http:
- pku2515 Birthday Cake
- http:
- pku1707 Sum of powers
- http:
- 12. 二分法
- 二分的思想还是很重要的，这里就简单推荐几个纯粹的二分题。
- * 简单：
- pku3273 Monthly Expense
- http:
- pku3258 River Hopscotch
- http:
- pku1905 Expanding Rods
- http:
- pku3122 Pie
- http:
- * 推荐：
- # pku1845 Sumdiv // 令a=p1^m1 * p2^m2 * ... * pk^mk, 那么由于因数和是一个积性函数,
- 所以 f(a)=f(p1^m1)*f(p2^m2)*.. ; f(x^t)=1+x+x^2+..+x^t=(1-x^(t+1))/(1-x);
- 由于mod 某个数，所以可以1/(1-x) 可以用同余数解决。不过注意如果MOD | x-1, 那么 f(x^t)=t+1 特殊处理一下。
- http:
- 13. 稳定婚姻问题
- 无意中接触到这个算法，还蛮有意思的，《组合数学》中有详细的介绍。
- pku3487 The Stable Marriage Problem
- http:
- zoj1576 Marriage is Stable
- http:
- 14. 数位类统计问题
- 在航点月赛中第一次接触到这类问题，scau 大牛little 龙推荐我看了一篇论文，09 年刘聪的《浅谈数位类统计问题》，这篇论文相当精彩，也相当详 细，每道题都有详细的分析和作者的参考代码。所以我也没什么可说的了，这些题的代码我博客里也就不贴了，大家直接去看论文吧。
- 简单：
- ural1057 Amount of degrees
- http:
- spoj1182 Sorted bit squence
- https:
- hdu3271 SNIBB
- http:
- 较难：
- spoj2319 Sequence
- https:
- sgu390 Tickets
- http:
- 以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码，由于比较麻烦就没加链接，需要的可以用我的站内搜索找到。
- 本小结会不断更新，转载请注明出处。
- 欧拉函数。
- # pku 3696 The Luckiest number
-
- http:
- 树状数组
- # hdu 3333
- 先求出每个位置后面和它一样的最近的那个数的位置next[i] ，然后用树状数组记录不重复的前n 个数的和，接着对询 问区间排序，从左到右做，记left 为在当前区间左边的那些数，通过树状数组，将left 到next[left]-1 之间的所有的数都减去 val[left] ，然后就可以直接像sum[i]-sum[j] 那样方便的求出区间里面没有重复的数的和。
- http:
- # pku 3222 // 树的dfs 和分治思想
- 解题报告见此：http:
- 本文来自CSDN博客，转载请标明出处：http:
·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150
- pku 1150 The Last Non-zero Digit
- 和计算排列数末尾有多少个零有些类似，把2，5因子都拿出来，剩下的数的最后一个数字只有1，3，7，9。只有各位上的数字才会影响最后一个非零数字。统计可以用递归来统计，求出1～n中因子2，5的个数，以及3，7，9结尾的数和去掉2，5后新的到的数中3，7，9结尾的数。结果就是 2^(dig[2]-dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9]) mod 10 ，用快速幂乘来算。
- pku 1186 方程的解数 (hash,枚举)
- 题目给出最多有6个未知数，未知数的取值在[1,150]之间，直接枚举时间复杂度是150^6，这个时间不能接受。枚举前一半的未知数可以到达的值(用hash表保存)，再枚举后一半，这样可以加快枚举。
- pku 1285 Combinations, Once Again（有重复的组合，dp）
- 对输入的数先统计一下，每个数出现的次数。如果每次重复的数，输出c[n][m]就可以。有重复数时，要考虑到取相同元素的情况，那么ans=sigma c[x][i]*z[s][m-i] 0<i<=m z[i][j]表示从1到第i堆中拿j个，把重复的数字表示成a[1],a[2]..,a[s],s个数出现重复。注意几个边界条件，c[0][0]=1,z[1][0...a[1]]=1,z[i][1]=i 2<=i<=s。
- pku 1430 Binary Stirling Numbers (stirling 数)
- 在wiki上找到公式，原来mod 2时和组合数有关系。原文如下：
- Using a Sierpiński triangle, it's easy to show that the parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:
- Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
- then mimic a bitwise AND operation by intersecting these two sets:
- to obtain the parity of a Stirling number of the second kind in O(1) time.
- pku 1465 Multiple(BFS,整除)
- 给几个一些数学，找出由这些数字组成的数中最小的一个能整除n的数。0<n<4999,把所有的数从小到大开始，在入队列前看下该数所到达的余数是否被前面小的数求到过，若否才入队。这样搜索的空间就只有n的剩余系了。
- pku 1715 Hexadecimal Numbers(组合)
- 不重复的组合问题，知道第几个找出这个组合。从最高位开始，一位一位确定dfs下去，每次都要保证已确定的位的所有组合不少于题目给出的序号。最多八层。
- pku 1737 Connected Graph(组合数学，高精度)
- 题目是求n个点用边链接，形成联通图的方案总算。满足联通的边数在[n-1,n(n-1)/2],自己一开始想分边数情况考虑，发现情况比较复杂，推出一个像整数拆分的方法。还来在网上看到一种更好的解法。公式是f[n]=f[k]*f[n-k]*c[n-2][k-1]*((2^k)-1) (c[n-2][k]表示组合数,1<=k<n);考虑一个完整的联通图，可以标记两个点1，2。将点1，点2分别划分在两个子联通图中分别为g1，g2。在g1中最少要有一个点与g2中的点2链接。这样的方式共2^k-1中，而g1总有c[n-2][k-1]个。将他们乘在一起就有了上面的式子。另外这题要用到高精度，终于用java写了个高精度的题感觉真方便。
- pku 1845 Sumdiv(积性函数，因子和)
- 求a^b的因子和(包括1和a^b),由于因子和是积性函数。所以f(a^b)=f(p1^t1)*f(p2^t2)...*f(pn^tn),对于f(p^t)的情况:
- f(p^t)=1+p+p^2+...+p^t=(p^(t+1)-1)/p-1。题目还要求mod 9901,这虽然是个素数，但是数据中出现了p-1 = 0 (mod 9901)的情况，这时f(p^t)=t+1 (mod 9901),要特殊处理下，其余用快速幂乘。
- pku 1809 Regetni（奇偶，组合）
- 根据 这个公式计算 A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2 三角形的面积是否为整数。这题不要去算具体的面积，答案和所选点的奇偶性有关，点的只有4种类型，(0,0),(1,1),(1,0),(0,1)。把这4类点的所有组合情况(共20种)代入公式
- 发现，当最少有两个点属于同一类型是面积才是整数。那么只有统计出所有点的组合情况就可以得出答案了。点的组合情况
- {0,1,2},{0,1,3},{0,2,3},{1,2,3},{0,1,1},{0,2,2},{0,3,3},{1,0,0},{1,2,2},{1,3,3},{2,0,0},{2,1,1},{2,3,3},
- {3,0,0},{3,1,1},{3,2,2},{0,0,0},{1,1,1},{2,2,2},{3,3,3} 这些是合理的组合。
- pku 1831 不定方程组(构造解)
- 这个题目很有意思，说a1+a2..an=s,1/a1+1/a2....+1/an=1;求一组这样的解。
- 为了找S的一组解，可以把S变小，来得到S的解。两种变小的方法:p/2+1/2=1 ,p*2+2=S;或p/2+1/3+1/6=1,p*2+9=S;选这两种方式是为了使奇数，偶数都有变小的方法。更重要的是当S一定大时，一定会有解。证明可以通过归纳来证得。所以事先保留一些小的S的解。大的S通过递归的构造出解来。
- pku 2142 The Balance(不定方程)
- 不定方程题，解a*x+b*y=d 。先求a*x0+b*y0=k。a/=k,b/=k,d/=k; 得到等价方程a'*x+b'*y=d'，一般解为x=x0-b'*t,y=y0+a't;其中t为任意整数。
- pku 2154 Color(波利亚定理,着色问题)
- 一个经典的着色问题，题目描述的是一个正常的旋转群，它的轮换指标为1/n*sigma(euler(d)*(xd)^(n/d)) ，其中d为n的所有因子。有了这个生成函数就可以容的计算n种颜色，在正n边形上着色的不同方案数了。
- pku 3352 In Danger(约瑟夫环)
- 简单题，和具体数学第一章提到的问题是一样的，讲每数2去掉一人，求胜利人的编号。公式是
- f(n)=f(n/2)*2-1 n=2*k
- f(n)=f(n-1/2)*2+1 n=2*k+1
- pku 2282 The Counting Problem(计数统计)
- 一个计算问题，统计a,b之间0-9这些数字出现的次数。可以分别计算f(b),f(a-1)的大小,其中 a<b f(n)表示1到n数字出现的统计。对于f(n) ，可以按位计算，从个位到n的最高位，分别计算0-9的个数，0的计算有些特殊，因为0不能是一个数字的最高位
- while(a>=times)
- {
- len=a/(times*10);
- for(i=0;i<10;i++)aa[i]+=len*times;
- if(len>0)aa[0]-=times;
- tmp=(a/times)%10;
- if(a>=times*10)start=0;else start=1;
- for(i=start;i<tmp;i++)aa[i]+=times;
- aa[tmp]+=a%times+1;
- times*=10;
- }
- pku 2429 gcd lcm Inverse
- 大数分解，要分解的数很大，到了2^63,普通的素数表方法行不通，要使用Pollard分解，分解lcm/gcd。需要注意的是会出现lcm==gcd的情况。
- pku 2769 Reduced ID Numbers(同余)
- 给出n个数，找一个数p,使得没个数mod p的值不相等。即n个数mod p不同余。先求出任意两个数的差(要正的),找个最小的数，使其不是前面求的差的约数。
- pku 2891 Strange Way to Express Integers(解模线性方程组)
- 这题是解个同余方程组，既解x= ai (mod bi) ,题目没有保证bi之间两两互素，所以中国剩余定理，在这里没用。可以通过先求
- 两个方程的解，这样就将两个方程和并成一个，直达只剩下一个为止就可以的到答案了。在合并的过程中有不能合并的情况出现就
- 说明整个方程组没有解。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1*x, a1+b1*x= a2 (mod b2),用扩展欧几里德求出c。两个方程就
- 可以用 c'= c (mod lcm(b1,b2))表示。
- hdu 1792 A New Change Problem
- 题是说：给两个互质的数，要求出两个数所不能组合出的正整数。在较大数的每一个等价类中找出最小的一数，它是较小数的倍数，那么在这个等价类中小于这个数的都是不能被表示出来的。最大的一个不能被表示出来的数是(n-1)*m-n 其中n>m,由于n有n个等价类，一个类包含不可表示出的数是m-1,总是是(n-1)*(m-1)/2
- pku 2888 Magic Bracelet(带约束的着色问题)
- 这题还是要用到波利亚定理，唯一的不同是计算矩阵的幂模，再求矩阵的迹。具体的推导就不知道是怎么来的。关于矩阵是指允许相邻的两种颜色之间有边，这就形成了个无向图。矩阵的n幂模，和快速幂乘的原理是一样的。
- pku 2917 Diophantus of Alexandria(不定方程，因数分解)
- 模拟下后发现，满足1/x+1/y=1/z的x，y是z的约数，并且x，y互素。统计x，y的对数再加1（x=z,y=z是特殊的一对）。
- 后来看到讨论里有公式，(x-z)(y-z)=z^2,计算小于z，并是z^2的约数就是答案了。
- pku2992 Divisors (组合数，因子个数)
- 计算C(n,k)的因子个数,由于n很小，最大为431，所以可以把1～431的所有数先因式分解，再来统计n*(n-1)...(n-k+1)/k*(k-1)...1的素因子个数。
- pku 3370 Halloween treats(鸽巢原理)
- 给定m个整数a1,a2,a3,..,am,存在整数k和l，0<=k<l<=m,使得ak+1 + ak+2 + ... +al能够被m整除。也就是说存在连续的一段al,...am,之和被m整除。考虑从a1...ai的和si，必定有si%m==0 或 si = sj (mod m),这种情况下取ai+1...aj,这段之和会是m的倍数。
- pku 3128 Leonardo's Notebook(置换)
- 题目意思是：一个置换是否可以由另一个置换的平方得来的。一个置换的平方，原来偶数长的循环会被分裂成两段长度相等的循环，而奇数长的循环不会被分裂。题目只是问是否存在，所以只要看所给置换中偶数长的循环是否成对，否则就不能由一个置换的平方得来。
- pku 3244 Difference between Triplets(公式变形)
- 很巧妙的公式变形，可惜不自己想出来的。首先计算max(a,b,c)-min(a,b,c)=(|a-b|+|b-c|+|a-c|)/2,有了这个公式就可以把比较变成加。那么
- D(Ta, Tb) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb}
- =(|Ia-Ib-Ja+Jb|+|Ja-Jb-Ka+Kb|+|Ia-Ib-Ka+Kb|)/2
- 令Ia-Ja=Wa,Ja-Ka=Ua,Ia-Ka=Ha;
- =(|Wa-Wb|+|Ua-Ub|+|Ha-Hb|)
- 将读入的数据转化W,U，H三个数组，分别计算这三个数组任意两个元素的差的绝对值之和。这里要用小于O(n^2)的算法，把数组排序后可以拿掉绝对值，统计每个元素作为减数出现的次数。
- pku 3324 Lucas-Lehmer Test(模运算)
- 首先要用到高精度，用java很方便。在计算模的时候，由于是mod 2^p-1,可以用移位来加速。
- a=r (mod 2^p-1) => a=k*(2^p-1)+r,先算个打概的k,得到的r>2^p-1,继续减2^p-1。这样比直接模运算要快。
-
- pku 3372 Candy Distribution(二次剩余系)
- 根据题目的意思可以得到方程 1+n(n+1)/2 =a (mod N),显然这是一个二次模方程。要看N的二次完全剩余系是否都有解。
- 结论是N要是2^x,x>=0,结论的证明还不知道。
- pku 3516 Hide That Number（高精度）
- 题目是说给出一个数y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆来就能得到答案了，可是y很大，构造的方法没有想到，最后还是暴力做的。每次在y的前面加个数学(1,2..9),或是加上10这两个数字，看新得到的数字是11的倍数。若是，就可以得到答案了。由于y很大，普通的高精度会超时，要增加进制。
- pku 3847 The Stable Marriage Problem（稳定婚姻）
- 稳定婚姻问题。用到了延迟认可算法。用最优方提出匹配，而被匹配者，不会立即接受，而是在提出要求者的集合中去掉，比当前着差的元素，知道没有人提出匹配，被匹配者才确定下匹配关系。值得一提的是，稳定婚姻的存在性不能被保证。
- pku 3358 Period of an Infinite Binary Expansion(数论，欧拉定理)
- 这个题目是求两个数相除p/q，结果的小数部分用二进制表示，当q不是2的幂时，这个二进制是个无线循环的01串。
- 下面是个模拟小数部分按二进制表示，可以发现二进制传一定会有循环，因为p=p%q,既然是循环，又是模运行，这和p模q的阶有关，p%q的阶一定是q的欧拉函数的因子。这样转换成一个模方程:p*2^n = x(mod q),当然p和q要互素，2和q互素。在计算前把q中的2去掉，p，q同除最大公因数。然后从1开始枚举，所以的欧拉数的因子。
- #include <stdio.h>
- #define pr printf
- int main()
- {
- int i,p,q;
- while(scanf("%d%d",&p,&q)==2){
- pr("0.");
- for(i=1;i<=100;i++)
- {
- p*=2;
- pr("%d",p/q);
- p=p%q;
- }
- pr("/n");
- }
- }
-
-
-
-
-
- pku 3590 The shuffle Problem(置换，数的分解)
- 题目求一个排列通过置换之后再回到原来的那个排列，对于给定的排列求出一个满足置换次数最多的一个置换。一个置换可以分解成多个循环，每次置换元素之和在同一个循环中的元素发生转换，同一个循环中循环节是元素的个数，所以这个题是要把一个数分成多个数的和，让这些数的最小公倍数最大。要保证lcd最大应该分解出来的每个数两两互素。由于数比较小，23是能最大的素数，所以直接枚举可以满足。
- pku 3641 Pseudoprime numbers(费马定理，快速幂乘)
- 简单题，先看p是否是素数，若是直接输出no。否则计算(a^p)%p,若结果是a输出yes，否则输出no。
- 2008哈尔滨赛区网络预选1007 The Luckiest number（欧拉定理运用）
- 题目说要找个数t，它的数字全是8，对于给定的n，t要是n的整数倍，求最小的t。
- 赛后才发现这题并不拿，可能是我太菜了。这题问题可以转换成8*(10^x-1)/9 = 0 (mod n ),这样就可以看出还有因子5和16的n是没有解的。并且n是偶数时，其解是n除去2因子的解。最后就是求解 10^x = 1 (mod 9*n) n是一个奇数，所以(10,n)=1,这样就可以根据欧拉定理 ,满足等式的解只能是 euler(9*n)的因子。枚举欧拉数的因子，最小的那个就是要求的解。由于n可以到2000000000，快速幂乘要支持64位运算。
- 2008 成都网络预选 1005 Farey Sequence Again(Farey Sequence ,构造)
- 与其说是数学题，还不如说是个模拟题。Farey Sequence序列规律性很强，暴力模拟后发现有很多规律。要用到的一个性质是
- Fn中连续的3个元素，a1/b1 ,a2/b2,a3/b3。若a1+a3<n 并且 b1+b3<=n ,则 a2=a1+a3,b2=b1+b3。这个性质很有用，根据它可以推出序列中前n项的分子不超过3，而且在构造的时候也要用到这个性质，找个第一个分母是2和3的元素的位置，都可以通过观察看出规律。序列就分成了3段，第一段分子只有1，第二段分子有1和2，而且是2，1，2，1，2，。。。这样循环的。第三段有1，2，3，也会出现循环，或是3，1，3，2 或是3，2，3，1这样的循环结。所以的规律都可以在模拟的序列中看出。只有3为分子时看不出规律，但是这样的元素左右两个一定是分子为1和2的两个元素，根据性质，知道3周围的两个元素的分母，就可以得出分子为3的元素的分母
- 2008 哈尔滨现场赛 Simple Addition Expression hdu2451
- 通过读题发现满足要求的数字，最高位由1，2，3组成，最低位由0，1，2组成，中间由0，1，2，3组成。计算小于n的数有多少个这种数就是答案。
- 2008 哈尔滨现场赛 K-dimension number hdu2447
- 读题后发现K要么是p,要么是p^2 (p为素数)，且p<=97,K维数n的情况只有三种。
- 一，当k为p时，n=(p')^(p-1)
- 二，当k为p^2时，n=(p1')^(p-1)*(p2')^(p-1)或n=(p1')^(p^2-1)
- 三，当k为1是，n=1。
- zoj 2562 More Divisors(反素数，dp)
- 反素数是指在不大于n数中含有最多约数，值最小的一个，比如2，4，6。。都是反素数。题目要求在小于10^16中的反素数。
- 由于反素数要求约数尽量多，所以素因子个数要尽量少，而指数要尽量大，这样一个数成为反素数的机会就大。所以只要考虑前13个素数所能组成的数就可以。转移方程
- f[i][j]= min{f[i-1][j/(k+1)]*p(i)^k}
- f[i][j] 表示i个素数，有j个约数的最小值。p(i)表示第i个素数,j%(k+1)==0
- 要注意的地方: j不超过50000。