算法学习笔记

中国剩余定理，Chinese Remainder Theorem，又称CRT，我们接下来就讲一下这个算法的原理。 要说原理，就得从古代说起。 （你到底是在讲编程课还是在讲历史课） （真的是在将编程课） 在古代，有一个问题，叫做“物不知数问题”，原文是这样的： 有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何？ 这个问题翻译过来就是问以下方程的所有正整数解： $ \begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases} $ 这个问题在后来有一个解了，解出来这个问题的人，编了一首诗，叫做“孙子歌诀”，原文： 三人同行七十稀 五树梅花廿一支 七子团圆正半月 除百零五便得知 这个解翻译过来就是说，若设 $r_3$ 为方程中 $x$ 模 $3$ 的余数，$r_5$、$r_7$ 同理，那么所有解 $x$ 一定满足： $x \equiv r_3 \times 70+r_5 \times 21+r_7 \times 15 \pmod{105}$ 其中 $105$ 的实际来源是上面三个方程的模数的 $\text{lcm}$，即 $\text{lcm}(3,5,7)=3 \times 5 \times 7=105$。 关于 $70$、$21$、$15$ 的来源下面再说，我们先证明一下这个解是正确的。 由于 $105$ 是三个模数的 $\text{lcm}$，所以说如果 $x$ 是满足条件的，$x-105$、$x+105$ 都是满足条件的（此处暂时忽略“正整数解”的限制），显然。 ...

有人问，组合数学不是就一些简单的公式吗？不是的，其实组合数学是数学中的一个非常庞大的分支，接下来就举一些例子。（更新中） 本文主要讲各种数据范围下，求组合数的方式；以及球盒模型各种情况下的公式；最后是一些球盒模型的扩展情况。 转到：球盒模型公式 转到：球盒模型扩展公式 （下面部分标题里的LaTeX公式更新后炸了，就凑合着看吧） 求组合数 以下所有范围都可以当成是以下题目的某个Subtask： 给你 $p$，代表模数。 之后会给你一个 $q$，代表询问次数。 每次询问给定 $n$ 和 $m$，问 $C_n^m \bmod p$ 的值。 下面不给定 $q$ 的范围，因为不重要。 以下全部默认 $n \geq m$。 范围1：$n,m \leq 2000,p \leq 10^9+7$ 先递推预处理，然后直接回答询问即可。 递推式：$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$。 预处理复杂度：$O(n^2)$ 查询复杂度：$O(1)$ 范围2：$n,m \leq 10^6,p \leq 10^9+7,p\text{ is prime}$ 1 先预处理阶乘，然后直接回答询问即可。 回答询问式：$C_n^m=\dfrac{n!}{m!(n-m)!}$。 为了节省时间复杂度，此处还可以预处理一下阶乘的逆元。 2 预处理复杂度：$O(n)$ 查询复杂度：$O(1)$ 范围3：$n,m \leq 10^6,p \leq 10^9+7$ 1 可以发现，范围2与范围3唯一的不同就是，范围3把质数的条件去掉了。 而把质数的条件后，就没法求逆元了，因为逆元可能不存在。 所以我们考虑换做法。 2 我们考虑把模数做个质因数分解，变成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。 ...