题解：P8749 [蓝桥杯 2021 省 B] 杨辉三角形

· · 题解

P8749 [蓝桥杯 2021 省 B] 杨辉三角形 Solution

提示

:::info[提示 1] 直接枚举太慢，不如采用估界法。 :::

:::info[提示 2] 考虑把组合数开始的地方列出来然后找规律。你会发现每一个“选几”的东西他的开始的项非常有规律。 :::

:::info[提示 3] 你会发现每个对角线上的数字是单调不减的，所以可以考虑二分。 :::

思路

我们会发现杨辉三角的性质，如图所示，杨辉三角每一项都对应一个组合数。

由于杨辉三角的左半部分和右半部分相同（即对称），由于是求第一次出现，可以把右半部分忽略，于是得到了下图。

注意到这堆对角线的开端都是 C_{2k}^{k}（k 为自然数），并且每条对角线上都是单调不减的，于是考虑二分。

我们发现 C_{17\times2}^{17}=C_{34}^{17} \approx 2.33\times10^9 > 10^9，而 C_{16\times2}^{16}=C_{32}^{16} \approx 6\times10^8 < 10^9，所以只需要枚举前 17 条对角线（0\sim16）。

然后你就会发现你枚举这 17 条对角线的时候每次都要做一次二分，所以时间复杂度为 \mathcal O(\log n)。

代码

还有神秘的代码环节。

:::success[Code] 仅展示主要代码。

for (int i = 16; i >= 0; i--) {
    int l = 2*i, r = INF;
    while (l <= r) {
        int mid = (l+r) >> 1, tmp = C(mid, i);
        if (tmp == n) {
            cout << (mid+1)*mid/2 + i+1 << endl;
            return 0;
        } else if (tmp < n)
            l = mid+1;
        else {
            r = mid-1;
        }
    }
}

:::

完了？
完了。
玩 florr 去喽～

记得三连哦～