小猫咪吃python

# 博弈论 博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。 博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。 -- 百度百科 # 公平组合游戏 公平组合游戏是博弈论的一种类型。它是一种特殊的棋类游戏，必须满足三点规则： 两名玩家交替行动； 游戏进行的任意时刻，可以进行的合法行动，与轮到哪名玩家无关； 不能行动的玩家判负； 其中规则 1 和 3...

# 组合数 从 n 个不同元素中取出 k 个元素的所有不同组合的个数，叫做从 n 个不同元素中取出 k 个元素的组合数，记做：CnkC_{n}^{k}Cnk​ 。 从 n 个元素取出 k 个元素，用公式表示可以写为：Cnk=n!k!(n−k)!C_{n}^{k} = \frac{n!}{k!{(n-k)!}}Cnk​=k!(n−k)!n!​ 。 # 问题 给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cab mod 109+7C_{a}^{b} \bmod 10^9+7Cab​mod109+7...

# 高斯消元法 高斯消元法 是数学上线性代数中的一种算法，可以把 矩阵 转换成 行阶梯型矩阵 。 高斯消元 可以用来找到形如下列的 多元线性方程组 的解： {a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2a31x1+a32x2+⋯+a3nxn=b3⋮am1x1+am2x2+⋯+amnxn=bm\left\{\begin{matrix} a_{11}x_1 + a_{12}x_2 + \dots +a_{1n}x_n=b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots +a_{2n}x_n=b_2 \\ a_{31}x_1 +...

阅读本文所需前置知识：欧几里得算法及其扩展，乘法逆元 # 中国剩余定理 中国古代的数学巨著《孙子算经》中提到一个 “物不知数” 问题，原文如下：” 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？“。 用现代语言解释，既，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。 现代数论中，中国剩余定理，是一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。 #...

# 最大公约数 若自然数 d ，同时是自然数 a 和 b 的约数，我们称 d 为 a 和 b 的公约数。而所有公约数中最大的，我们称为 a 和 b 的最大公约数，记为 gcd(a,b) 。 求最大公约数的算法有很多，比如：分解质因数、九章算术里的更相减损术、短除法等等。但是应用最广泛的还是今天的主角 -- 辗转相除法。 # 辗转相除法 古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以又被命名为欧几里得算法。 辗转相除法依赖除法的一个基本性质（下面称为除法性质）： 假设 d|a ，同时 d|b ，那么一定有 d|(ax+by) 。 其中 |...

阅读本文所需前置知识：快速幂 # 数论中的逆元 乘法逆元：已知 b,m 互质，并且对于任意整数 a ，如果满足 b 可以整除 a （即 a 是 b 的倍数），则存在一个整数 x ，使得 a/b≡a∗x(modm)a/b \equiv a*x\pmod{m}a/b≡a∗x(modm) ，则称 x 为 b 的模 m 乘法逆元，记为b−1(modm)b^{-1}\pmod{m}b−1(modm)。 (注意这里的 - 1 作为一个标记，用来表示逆元，而非指数。) b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2b^{m - 2}bm−2 即为 b...

# 快速幂 快速幂，又叫欧拉降幂。它的作用也很简单，就是快速的求出ak mod pa^k \bmod pakmodp 的值。 # 问题 给出 n 组数 a,k,pa, k, pa,k,p ，每组数据都求出 ak mod pa^k \bmod pakmodp 的值是多少。 # 数据范围 1≤n≤1000001 \le n \le 1000001≤n≤100000 1≤a,k,p≤2∗1091 \le a,k,p \le 2 * 10^91≤a,k,p≤2∗109 # 分析 从问题出发。因为 a 和 k 的范围都很大，最大可以到 2∗1092 * 10^92∗109...

# 欧拉函数 欧拉函数：数字 1~n 中与 n 互质 的数的 个数 ，记为φ(n)\varphi(n)φ(n)。 互质的数：公约数只有 1 的两个数。 例如：φ(12)=4\varphi(12)=4φ(12)=4，其中 1~12 中共有 4 个与 12 互质的数，分别是 1，5，7，11 。 # 如何求欧拉函数？ # 一个重要性质 这里我们依赖欧拉函数的一个重要性质欧拉函数是一个积性函数，也就是当 n 与 m 互质时，公式φ(nm)=φ(n)∗φ(m)\varphi(nm)=\varphi(n)*\varphi(m)φ(nm)=φ(n)∗φ(m) 成立。 # 求解方案 首先，对 n...

# 质数 质数又叫素数，是指在大于 1 的自然数中，除了 1 和它本身以外不在有其它因数的自然数。2 是最小的质数。 因数是指整数 a 除以整数 b (b≠0) 的商正好是整数而没有余数，我们就说 b 是 a 的因数。 # 判断一个数 n 是否是质数 明确概念之后，接下来的问题是如何判定某个数是否是质数呢？ 一个标准的方式是使用试除法。 # 试除法 用 n 除以 2 到 n\sqrt{n}n​ 的所有整数，若其中没有可以整除的，则可以认定 n 是一个质数。 这里有一个问题是为什么试除法判断到 n\sqrt{n}n​ 就可以，而无需除到 n...

# 贪心算法 贪心算法是最常见的算法之一，并且是为数不多的可以从名字上体现思想的算法。 可以用这种算法解决的问题，常常是证明难度较大，但是代码好写的问题。 # 什么样的问题可以使用贪心思路 贪心算法体现的地方在于，该算法只考虑当前的状态下的最优结果，而不是去从全局思考问题，这就是贪心两个特性之一具有最优局部结构。 并且在贪心算法中已经确定的结果，就不可被其后的状态再次影响，也就是两个关键特性中的另外一个无后效性。 # 贪心和动态规划的区别 # 解决的问题类型不同 一个比较明显的区别是，贪心算法不依赖子问题，而动态规划的状态转移是通过子问题一步步转移到最终问题 。 #...