Oiclass PU2TI P3846 杨辉三角题解

打表+卡常题

思路

不难发现，最短路径不外乎以下两种可能：

image-20231216150315312

一种是先一直向下，再一直向右下；而另一种是先一直右下再一直向下。对于 \(k \leq \frac{n}{2}\) 的请况，很显然是选择第一种路线，否则是第二种路线。

我们可以通过一个简单的技巧来将两种路线合一，我们可以发现，其实第二种情况相当于第一种情况中将 \(k\) 改为 \(n - k + 1\) 的情况（像抬杠的可以自己去算一下，这个是真的，怎么证的还在想）。那么我们可以只考虑第一种情况。

首先是值为 \(1\) 的那一段路径，很容易发现，由于他是走到 \(n - k\) 层的，因此这段路径的数字之和为 \(1 \times (n - k)=n - k\) 。接下来考虑如何计算剩下部分的数字和。没有头绪？那就打表吧！于是我们对于从 \((1,\, n - k)\) 到 \((n, k)\) 的路径和记为 \(f_{n,\, k}\) ，我们可以计算出这样的一个 \(f\) 数组：

image-20231216152605743

有眼睛就能看出来，\(f_{i,\,j} = {i \choose j-1}\) 。那么这就好办了啊，直接计算即可！

但是怎么算呢？我们如果直接计算组合数，很明显复杂度（含逆元的计算）是 \(\mathcal{O}(k\log p)\) 的。在题目 \(1 \leq n, k, p \leq 10^9\) 的数据范围下，你不超时谁超时（除非评测机单核性能起飞）！那么我们此时可以考虑使用 Lucas 定理 ，下面简述一下 Lucas 定理的内容（\(p\) 为质数）： \[ {\rm Lucas}(n,\, m,\,p) = {n \choose m}\, {\rm mod}\,p = \left\{ \begin{array}{l}1\,\,\,\,\,m=0 \newline {n\, {\rm mod} \,p \choose m\,{\rm mod\, p}} \times {\rm Lucas}(n \div p,\, m \div p,\, p)\,{\rm mod} \, p \end{array} \right. \] 通过这个定理，我们可以在 \(\mathcal{O}(\log ^2 p)\) 左右的时间求出组合数取模的值（含逆元）。

下面我们再来讲一下其中的组合数又要怎么求？

我们可以将正常的组合数程序加上取模，就像这样：

int C(int n, int m, int p) {
    if (n < m) {
        return 0;
    }
    if (m > n - m) {
        m = n - m;
    }
    int a = 1, b = 1; // a 为分子、b 为分母
    for (int i = 0; i < m; i++) {
        a = (a * (n - i)) % p;
        b = (b * (i + 1)) % p;
    }
    return ((a % p) / (b % p)) % p;
}

然后尝试带入某一个数，然后……错啦啊啊啊！原因也非常的简单，我们考虑此时有两个数：\(a=4\)，\(b=2\)，计算 \(a \div b \, {\rm mod} \, 2\) 的值，如果先将分子分母取模，那么直接就无意义了，但是很显然这个式子的答案为 \(0\) 。

为了解决这个问题，我们将引入一个东西，称为逆元。我们可以这样理解，根据小学的知识，除以一个数等于乘以它的倒数，也就是说 \(a \div b = a \times \frac{1}{b}\) 。而我们假设 \(x\) 的倒数为 \(\frac{1}{x}\) ，很容易发现 \(x \times \frac{1}{x} = 1\) 。也就是说，我们可以这样定义：一个数和另一个数的乘积为 \(1\) ，则成这两个数互为倒数。那么我们可以尝试将这个概念往模运算推广，我们可以尝试定义一个模 \(p\) 意义下的倒数，假定 \(x\) 为 \(a\) 的倒数，那么： \[ ax \equiv 1\, {\rm mod}\, p \] 此时我们称 \(x\) 为 \(a\) 的乘法逆元，记为 \(a^{-1}\) 。

那么下一步我们考虑如何求解乘法逆元，根据 费马小定理 ，我们可以得知：若 \(p\) 为质数且 \(a\) 与 \(p\) 互质（\(\gcd(a,\, p)=1\)），则 \(a^{p-1} \equiv 1\,{\rm mod} \, p\) 。又因为 \(ax \equiv 1 \,{\rm mod} \,p\) ，所以 \(ax \equiv a^{p-1}\,{\rm mod} \, p\) 。又根据 同余的性质 ，可知 \(x \equiv a^{p-2} \, {\rm mod }\, p\) 。至此，我们可以再次化简以下，借助同余方程的一个特殊解，计算出 \(a\) 在模 \(p\) （\(p\) 为质数）意义下的逆元，即 \(a^{-1} = a^{p - 2}\) 。

根据上面的式子，我们就可以在 \(\mathcal{O} (\log p)\) 的时间复杂度内计算出逆元（借助快速幂）。那么我们就可以将组合数的代码改成这样：

int C(int n, int m, int p) {
    if (n < m) {
        return 0;
    }
    if (m > n - m) {
        m = n - m;
    }
    int a = 1, b = 1;
    for (int i = 0; i < m; i++) {
        a = (a * (n - i)) % p;
        b = (b * (i + 1)) % p;
    }
    return (int)(a * qpow(b, p - 2, p)) % p;
}

至此，我们已经完成了题目的所有推导，实现即可。

实现：

看起来，我们只需要在模板的基础上，调用一下函数输出即可。但是，如果你提交一下就会发现，你获得了 \(40 \rm pts\) 的好成绩！啊？！不是时间复杂度能过吗？是的，但是需要常数优化！

我们观察一下代码，发现其中包含大量的递归及除法（含取模）内容。对于 long long \(64\) 位的大小来说，这些除法和内存寻址实在是太慢啦！因此，我们只需要关闭 long long 即可 AC

AC Code :

#include <iostream>

//#define int long long
#define endl '\n'

using namespace std;

int qpow(int a, int b, int p) {
    int ans = 1;
    a %= p;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
        b >>= 1;
        a = (a * a) % p;
    }
    return ans % p;
}

int C(int n, int m, int p) {
    if (n < m) {
        return 0;
    }
    if (m > n - m) {
        m = n - m;
    }
    int a = 1, b = 1;
    for (int i = 0; i < m; i++) {
        a = (a * (n - i)) % p;
        b = (b * (i + 1)) % p;
    }
    return (int)(a * qpow(b, p - 2, p)) % p;
}

int Lucas(int n, int m, int p) {
    if (m == 0) {
        return 1;
    }
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

int t, n, m, p;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> m >> p;
        n += 1;
        m += 1;
        m = min(m, n - m + 1);
        cout << (n - m + Lucas(n, m - 1, p)) % p << endl;
    }
}