OI中的一些思想在高考数学中的应用

by Midoria7

前言

最*的数学学案中，出现了许多和信息学竞赛中一些思想挂钩的题目，在这里一并整理出来，虽然可能对大家在做题上没有特别的提分作用，但是也能够希望给大家提供一个新的思考问题的角度。作为对文化课帮助最低甚至自带文化课 -- buff 的信息竞赛，今天我也是要证明他对高考课学习也是有帮助的（滑稽）

卡特兰数

对这个的介绍要从这道题说起。

（全国\(Ⅲ\)卷2016 理12）定义 “规范 \(01\) 数列” \({a_n}\) 如下：\({a_n}\) 共有 \(2m\) 项，其中 \(m\) 项为 \(0\)，\(m\) 项为 \(1\)，且对任意\(k ≤ 2m\)，\(a_1\)，\(a_2\)，\(…\)，\(a_k\)中 \(0\) 的个数不少于 \(1\) 的个数，若 \(m = 4\)，则不同的 “规范 \(01\) 数列” 共有 _______ 个。

这道题的答案是 14，大家应该都有印象，战普老师讲大概方法就是枚举，或者两个一起，四个一起枚举。由于 \(m\) 较小，所以这种方法是可行的。

但如果 \(m\) 较大的话，枚举显然就变得不切实际，我们需要一个通项公式来解决这个问题。

事实上如果我们把 \(0\) 抽象成 \(x\) 轴，\(1\) 抽象成 \(y\) 轴，这道题可以转化为如下问题：从 \((0,0)\) 走到 \((4,4)\)，只能走整数点，每次走一个单位长度，且行走路径全程在直线 \(y = x\) 下方（不穿越但可以碰到）的合法非降（只能向上或向右走）路径数。

这样显然就变成了一个组合数问题。由于 “不穿越但可以碰到” 这个条件较难转化，我们把它转化为 “不能触碰直线 \(y = x + 1\)”。

正难则反。显然，若没有这个不能触碰直线的要求，方案数则是 \(C_{2m}^m\)。

下面我们计算不合法路径数。对于和直线 \(y = x + 1\) 相碰的路径，我们以碰到一下为例，将这些直线在相碰点之后的路径关于 \(y = x + 1\)，那么这些直线的终点均为 \((4,4)\) 关于 \(y = x + 1\) 的对称点 \((3,5)\)。更多相碰点的路径也是一样，都会一一对应。而所有从 \((0,0)\) 到 \((3,5)\) 的路径，都会与 \(y = x + 1\) 相碰。因此我们知道，不合法的路径数就是从 \((0,0)\) 到 \((3,5)\) 的路径数，即 \(C_{2m}^{m-1}\)。

因此我们得到本题的答案就是 \(C_{2m}^m - C_{2m}^{m-1}\)。代入 4 得到答案 14。

\(a_m = C_{2m}^m - C_{2m}^{m-1}\)，这个就是在组合数学中一个很有名的数列，即卡特兰数列，将其化简后还能得到它的另一个形式：\(a_m = \cfrac{C_{2m}^m}{m-1}\)。

卡特兰数（英语：Catalan number），又称卡塔兰数、明安图数，是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。1730年左右被蒙古族数学家明安图使用于对三角函数幂级数的推导而首次发现，1774年被发表在《割圜密率捷法》。

以下这些问题的答案，都是相对应的卡特兰数。

1.有 \(2n\) 个人排成一行进入剧场。入场费 5 元。其中只有 \(n\) 个人有一张 5 元钞票，另外 \(n\) 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？

2.一位大城市的律师在她住所以北 \(n\) 个街区和以东 \(n\) 个街区处工作。每天她走 \(2n\) 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

3.在圆上选择 \(2n\) 个点，将这些点成对连接起来使得所得到的 \(n\) 条线段不相交的方法数？

4.对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？

5.一个栈（无穷大）的进栈序列为 \(1,2,3,\dots ,n\) 有多少个不同的出栈序列？

6.\(n\) 个结点可够造多少个不同的二叉树？

7.给定 \(n\) 对括号，求括号正确配对的字符串数。

错排问题

考虑这样一个问题：

\(n\) 封不同的信，编号分别是 \(1, 2, 3,\cdots, n\)，现在要把这五封信放在编号 \(1, 2, 3,\cdots, n\) 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

像学案上给的 \(n = 3\)，直接枚举就可以得到。而若 \(n\) 较大应该怎么做？

假设我们考虑到第 \(n\) 个信封，初始时我们暂时把第 \(n\) 封信放在第 \(n\) 个信封中，然后考虑两种情况的递推：

• 前面 \(n-1\) 个信封全部装错；
• 前面 \(n-1\) 个信封有一个没有装错其余全部装错。

对于第一种情况，因为前面 \(n-1\) 个已经全部装错了，所以第 \(n\) 封只需要与前面任一一个位置交换即可，总共有 \(f[n-1] \times (n - 1)\) 种情况。

对于第二种情况，前面 \(n-1\) 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 \(n-1\) 个信封中如果有一个没装错，那么我们把那个没装错的与 \(n\) 交换，即可得到一个全错位排列情况。

其他情况，我们不可能通过一次操作来把它变成一个长度为 \(n\) 的错排。

于是可得错位排列的递推式为 \(f[n] = (n - 1)(f[n - 1] + f[n - 2])\)。

错位排列数列的前几项为 0，1，2，9，44，265。

同余

同余式是数论的基本概念之一，这个数学奥赛的同学应该也会很熟悉。它的定义如下：

若 \(a = b + km (k ∈ Z)\)，则称 \(a\) 与 \(b\) 关于 \(m\) 同余，记为 \(a \equiv b (\mod m)\)，其中 \(m\) 称为模数。

小知识：在大部分编程语言中，取模运算的符号是 "%"，因为“模”谐音“膜拜”，所以如果有一个 OIer 给你发了一串 "%%%"，这并不是文明和谐，而是对您表示由衷的敬意。

运算法则

同余式满足的运算法则有：

• 自反性
• 对称性
• 传递性
• 同加性
• 同乘性
• 同幂性
• 不满足同除性

计算余数问题

给一个典型例题：

计算 \(3 ^ {89}\) 被 \(7\) 除的余数。

即求 \(3^{89} \mod 7\) 的结果。

如果不用排列组合的知识，用同余怎么解决这个问题呢？

首先，根据二进制，所有十进制的自然数都能分解为 2 的幂方的和，这个过程叫做二进制拆分。

\(3^1 \equiv 3(\mod 7)\)

\(3^2 \equiv 3^2(\mod 7) \equiv 2(\mod 7)\)

\(3^4 \equiv (3^2)^2(\mod 7) \equiv 2^2(\mod 7) \equiv 4\)

\(3^8 \equiv (3^4)^2(\mod 7) \equiv 4^2(\mod 7) \equiv 2\)

\(3^{16} \equiv (3^8)^2(\mod 7) \equiv 2^2(\mod 7) \equiv 4\)

\(3^{32} \equiv (3^{16})^2(\mod 7) \equiv 4^2(\mod 7) \equiv 2\)

\(3^{64} \equiv (3^{32})^2(\mod 7) \equiv 2^2(\mod 7) \equiv 4\)

\(3^{89} \equiv 3^{64} \times 3^{16} \times 3^8 \times 3^1(\mod 7) \equiv 96(\mod 7) \equiv 5(\mod 7)\)

所以我们计算出来的答案是 5。

当我们使用排列组合方法解决余数问题时，如果像求 \(6^{89} \mod 7\) 的结果会很简单，因为其可以转化为 \((7 - 1)^{89} \mod 7\)，这样最终结果中会出现一个 1。

但是如果像 \(3^{88} \mod 7\) 这种问题，若将其转化为 \(9^{44} \mod 7\) 即 \((7 - 2)^{44} \mod 7\)，这样最终你还需要计算 \(2 ^ {44} \mod 7\)。（或者还有其他更高级的方法我不会 orz）。而如果是 \(3^{89} \mod 7\)，用排列组合方法计算会更麻烦。这时就体现了同余的优越性。

参考实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    int ans = 1;
    for (; n; n >>= 1, m = (long long) m * m % k)
        if (n & 1) ans = (long long) ans * m % k;
    cout << ans << endl;
    return 0;
}

中国剩余定理（孙子定理）*

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求满足以下条件的整数：除以 \(3\) 余 \(2\)，除以 \(5\) 余 \(3\)，除以 \(7\) 余 \(2\)。

中国剩余定理（CRT）可求解如下形式的一元线性同余方程组（其中\(n_1,n_2,\dots,n_k\)两两互质）。

• 计算所有的模数的积\(n\)；
• 对于第\(i\)个方程：
  • 计算 \(m_i=\cfrac{n}{n_i}\)；
  • 计算 \(m_i\) 在模 \(n_i\) 意义下的逆元 \(m_i^{-1}\)；在这里，需要使用 exgcd 计算逆元。
  • 计算 \(c_i=m_im_i^{-1}\)（不要对 \(n_i\) 取模）
• 方程的唯一解为： \(a=\sum\limits^k_{i=1}a_ic_i\pmod n\)

期望的线性性质

对于两个随机变量 \(X,Y\)，\(E(X + Y) = E(X) + E(Y)\)。

这个式子表现了期望的线性性质。具体证明非常麻烦，这里给出一个链接大家可以了解。这里只给出这个性质的应用。

清零次数

先来一个高端大气上档次的题：

CF280C 给定一棵节点数为 \(k\) 有根树，每次随机选一个未被删除的点，将以它为根的子树删除。求删除整棵树所用的期望步数。

可能会把大家看懵，下面把他转化成一个我们在数学作业上看到的题。

输入一个数 \(k\)，按下回车可以把它转化为一个比他小的自然数。求将数 \(k\) 最终转化为 \(0\) 的期望步数。

首先解释一下出现数 \(n\) 的概率为什么是 \(\cfrac{1}{n + 1}\)。对于一个数 \(n\)，我们在转化到 \(n\) 之前选到的所有数对 \(n\) 能否被选到的概率实际上是没有影响的。而当未转化的序列中只剩 \(n\) 及比其小的数时，若 \(n\) 能被选到，当且仅当数 \(0,1,2,\cdots,n - 1\) 均没有被选到，而选择 \(n\)。则概率为 \(\cfrac{1}{n + 1}\)。

所以根据期望的线性性，数 \(k\) 被清零的期望步数为 \(\sum\limits_{i = 0}^{k - 1}\cfrac{1}{i + 1}\)。

超几何分布的期望公式

构造一个简单的超几何分布情景。在一个盒子中有 \(a\) 个黑球和 \(b\) 个白球，不放回地取 \(n\) 次球（\(n ≤ a + b\)），求取出的黑球数的期望个数。

其实无论是超几何分布还是二项分布，其本质都是 Pólya 罐子模型。下面对其进行一个简单的解释，更严谨的证明请看上面的链接。（点一下，玩两年）

在第一次取球时，取出黑球的概率是 \(\cfrac{a}{a+b}\)，取出白球的概率是 \(\cfrac{b}{a+b}\)。取出球后，盒子中剩余黑球的期望个数为 \(a -\cfrac{a}{a+b}\)，剩余白球的期望个数为 \(b -\cfrac{b}{a+b}\),可以看出黑球白球的期望个数比仍为 \(a : b\)，因此第二次取球时取出黑球的概率仍是 \(\cfrac{a}{a+b}\)，取出白球的概率仍是 \(\cfrac{b}{a+b}\)。

根据期望的线性性，将每一次取出黑球的期望累加，得到超几何分布的期望公式 \(E(X) = n\cfrac{N}{M}\)。

概率与期望动态规划 *

简称概率 DP，这个战普在小学期提到过一次。

（这个部分已经咕掉了）

牛顿迭代法求*似*方根

在做导数相关的题目时，我们经常需要评估某些数*似值。对于一些数的*方根，我们可以用牛顿迭代法来估算他的*似值。

初始时我们从给定的 \(f(x)\) 和一个*似解 \(x_0\) 开始。（\(x_0\) 的值可任意取）

假设我们目前的*似解是 \(x_i\)，我们画出与 \(f(x)\) 切于点 \((x_i,f(x_i))\) 的直线 \(l\)，将 \(l\) 与 \(x\) 轴的交点横坐标记为 \(x_{i + 1}\)，那么这就是一个更优的*似解。重复这个迭代的过程。 根据导数的几何意义，可以得到如下关系：

整理后得到如下递推式：

如果 \(f(x)\) 比较*滑，那么随着迭代次数的增加，\(x_i\) 会越来越逼*方程的解。牛顿迭代法的收敛率是*方级别的，这意味着每次迭代后*似解的精确数位会翻倍。

我们尝试用牛顿迭代法求解*方根。设 \(f(x) = x ^ 2 - n\)，这个方程的*似解就是 \(n\) 的*似值。于是我们得到

实现代码：

#include <bits/stdc++.h>
using namespace std;

double sqrt_newton(double n) {
  const double eps = 1E-15;
  double x = 1;
  while (true) {
    double nx = (x + n / x) / 2;
    if (abs(x - nx) < eps) break;
    x = nx;
  }
  return x;
}

int main() {
    double x;
    cin >> x;
    printf("%.12lf", sqrt_newton(x));
    return 0;
}

运行结果：

后记

最后希望大家能够好好感受数学之美。

部分参考文献：

信息学奥赛之数学一本通（林厚从）

https://oi-wiki.org/math/

https://www.cnblogs.com/Midoria7/p/Math.html （这是我自己的博客！）