保研考研机试攻略：第三章——数学（3）
🍦🍦🍦今天我们继续来看数学的最后一部分，感谢大家对该专栏的支持，我会继续努力学习更新的，期待大家与我共同进步，我们一起拿捏机试~~~
目录
🧊🧊🧊3.8 二分快速幂
🥥例题：DreamJudge 1017
🧊🧊🧊3.9 常见数学公式总结
错排公式
海伦公式
组合数公式
两点之间的距离公式
扇形面积
卡特兰数
🧊🧊🧊3.10 规律神奇OEIS
🥥例题：DreamJudge 1479
🧊🧊🧊3.8 二分快速幂
有一类题目是这样的：求 (x^y) % p
当 y 很大的时候，我们不能直接用for循环一个一个乘，因为这样的方法复杂度是 O(N)。
遇到这类问题的时候，我们可以使用二分快速幂的方法来求解。
举个例子：3^7 = 3^4 * 3^2 *3^1
首先我们要知道，对于任意一个数 s，它的二进制代表了它可以由 2 的次幂的累加和来表示。
比如 7 的二进制是 111，那么它就是说 7 = 2^2 + 2^1 + 2^0 ；再比如一个数 12 的二进制是 1101 13 = 2^3 + 2^2 + 2^0
所以对于任意一个 x^y，我们都可以将 y 分解成 2 的幂次的形式，例如 5^13 = 5^8 * 5^4 * 5^1
这样做的好处是：1..2..4..8..16..32..64..128........1024.....
1、每一个数都是它前一个数的 2 倍
2、它的迭代速度超级快
🥥例题：DreamJudge 1017
运用上面讲的二分快速幂和同余模定理即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod_pow(ll x, ll y, ll mod) {ll res = 1;while (y > 0) {//如果二进制最低位为 1、则乘上 x^(2^i)if (y & 1) res = res * x % mod;x = x * x % mod; // 将 x 平方y >>= 1;}return res;
}
int main() {ll x, n;//注意 x*x 会超出 int 范围scanf("%lld%lld", &x, &n);printf("%lld\n", mod_pow(x, n, 233333));return 0;
}🧊🧊🧊3.9 常见数学公式总结
错排公式
问题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
递推公式为：D(n) = (n - 1) * [D(n - 1) + D(n - 2)]
海伦公式
S = sqrt(p * (p - a) * (p - b) * (p - c))
公式描述：公式中 a，b，c 分别为三角形三边长，p 为半周长，S 为三角形的面积。
组合数公式
公式描述： 
组合数公式是指从 n 个不同元素中，任取 m(m≤n)个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。
两点之间的距离公式
公式描述：公式中(x1，y1)，(x2，y2)分别为 A、B 两个点的坐标。
扇形面积
S=1/2×弧长×半径，S 扇=（n/360）πR²
卡特兰数
原理
令 h(0)=1,h(1)=1,catalan 数满足递归式：
(其中 n>=2)
另类递推公式： 
该递推关系的解为：
(n=1,2,3,...)
卡特兰数的应用实质上都是递归等式的应用
前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
所有的奇卡塔兰数 Cn 都满足 n = 2^k-1、所有其他的卡塔兰数都是偶数。
应用
- 12 个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
- 括号化问题。矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
- 将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数?
- 出栈次序问题。一个栈(无穷大)的进栈序列为 1、2、3、...、n，有多少个不同的出栈序列?
- 通过连结顶点而将 n + 2 边的凸多边形分成三角形的方法个数。
- 所有在 n*n 格点中不越过对角线的单调路径的个数。
- 有 n+1 个叶子的二叉树的个数。
更多的变化不胜枚举，遇到这类规律题建议使用下一节讲的 OEIS 来解决问题。
🧊🧊🧊3.10 规律神奇OEIS
使用OEIS，你可以飞快解出那些所谓推公式的规律难题，但是需要进入网站才可，所以如果考试不允许切换网页就不要用这种方法了。
它的网址：http://oeis.org/
只要你输入前几项，它就可以给你找出规律来，并且自动给你推出公式。所以对于找规律的题目，你只需要手动计算出前几项的值，或者暴力打表求出前几项的值，然后输入 OEIS，他就可以告诉你公式是什么。
接下来，我们就用这个神器来练练手~
🥥例题：DreamJudge 1479
对于这类让我们去找有多少种情况的题目，第一反应就是他是有规律的，它的规律可能简单，也可能很难。这时候我们先推出它的前几项值，n 为 1 时答案等于 1，n 为 2 时答案等于 2，n 为 3 时答案等于 3，n 为 4 时答案等于 5。然后我们将这前几项值 1,2,3,5 输入到OEIS 中，它立马告诉我们这个规律是斐波那契数列，f[i]=f[i-1]+f[i-2]。
#include <stdio.h>
long long f[10005] = {0};
int main(){int n;scanf("%d", &n);f[0] = 1; f[1] = 1;for (int i = 2; i <= n; i++) {f[i] = f[i-1] + f[i-2];f[i] %= 2333333;}printf("%lld\n", f[n]);return 0;
}创作不易，点个赞吧~点赞收藏不迷路，感兴趣的宝子们欢迎关注该专栏~
勤奋努力的宝子们，学习辛苦了！🌷🌷🌷休息下，我们下部分再见👋( •̀ ω •́ )✧~