【学习7】计数与数学推导 - 专题补充练习

想必大家在之前做题的时候也做过很多计数题。那么计数题是怎么做的呢？你需要用到下面这两条基本的原理： - **加法原理**：如果做一件事情有两类方式，第一类方式有 $n$ 种方法，第二类方式有 $m$ 种方法，那么做这件事情总共有 $n+m$ 种方法。 - **乘法原理**：如果做一件事情分为两步，第一步有 $n$ 种方法，第二步有 $m$ 种方法，那么做这件事情总共有 $n\times m$ 种方法。 现在，你已经掌握了计数的基本原理了，就让我们看一看下面这个简单的例子，来把我们刚刚学到的东西运用到实践中吧。 - P5291 [十二省联考2019]希望 ……显然我们不能真这么搞。下面是一些真正的入门题。 #### 真的只是加法原理和乘法原理而已 - P1192 台阶问题 - P1287 盒子与球 - P1025 [NOIP2001 提高组] 数的划分 - P3197 [HNOI2008]越狱 - P1655 小朋友的球 #### 一些计算方法 考虑到如果只会推式子，推完不会算的话，题还是做不出来。所以这里还是先放上你谷有的一些计算方法的模板，先确保拿到一个能算的式子之后会算。 - P1226 【模板】快速幂||取余运算 - P3811 【模板】乘法逆元 - P2613 【模板】有理数取余 - P5656 【模板】二元一次不定方程 (exgcd) - P1939 【模板】矩阵加速（数列） - P4777 【模板】扩展中国剩余定理（EXCRT） - P3383 【模板】线性筛素数 - P3807 【模板】卢卡斯定理/Lucas 定理 - P6178 【模板】Matrix-Tree 定理 #### 组合计数 有用的东西：[组合数学 on OI wiki](https://oi-wiki.org/math/combinatorics/combination/) （可以从这里一直读完组合数学整段） [fhq_treap 讲卡特兰数的博客!](https://www.cnblogs.com/dixiao/p/15233775.html) - P1313 [NOIP2011 提高组] 计算系数 - P2822 [NOIP2016 提高组] 组合数问题 - P1044 [NOIP2003 普及组] 栈 - P1641 [SCOI2010]生成字符串 - P6162 [Cnoi2020]四角链 - P6620 [省选联考 2020 A 卷] 组合数问题 - P1450 [HAOI2008]硬币购物 - P5824 十二重计数法 // 水平不太够的话可以不全做，不过最好还是熟悉一下一些经典的模型 - P5748 集合划分计数 // 同理，可以写点部分分 #### 数论 数论是研究整数的理论，以整除性作为其核心。 有用的东西：[数论 on OI wiki](https://oi-wiki.org/math/number-theory/basic/) （同上，可以一直读完整段） - P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 - P1403 [AHOI2005]约数研究 - P1372 又是毕业季I - P1134 [USACO3.2]阶乘问题 - P2261 [CQOI2007]余数求和 - P6583 回首过去 - P2158 [SDOI2008] 仪仗队 - P2155 [SDOI2008] 沙拉公主的困惑 #### 杂七杂八的题 没有什么统一方法，但都需要进行一些数学推导。 - P1357 花园 - P5023 [NOIP2018 提高组] 填数游戏 - P7116 [NOIP2020] 微信步数 - P5472 [NOI2019] 斗主地 - P2606 [ZJOI2010]排列计数 - P6657 【模板】LGV 引理 - P6026 餐馆 - P6130 随机红包 - P3343 [ZJOI2015]地震后的幻想乡 - P2059 [JLOI2013]卡牌游戏 - P4769 [NOI2018] 冒泡排序 - P6478 [NOI Online #2 提高组] 游戏 - P4774 [NOI2018] 屠龙勇士 - P1654 OSU! 当然，你也可以尝试把上面那个假入门题做了。 如果你实在不会了也可以考虑打表找规律：[WYXkk 的日报](https://www.luogu.com.cn/blog/WYXkk/zhao-gui-lv-zong-ru-men-dao-ru-tu) #### 一些扩展 适合想要挑战自我的同学，由于不在 NOIp 范围内所以不做展开，有兴趣可以自己去了解 - 组合数学，可以去读《具体数学》 - 多项式与生成函数 - 数论筛法