题解：P12876 [蓝桥杯 2025 国 Python A] 杨辉三角

· · 题解

提供一种简单的想法

注意到红色这个圈内，数字单调递增，即 f(x)={x \choose 1} 单调递增；蓝色这个圈内，数字单调也是递增，即 f(x)={x+k-1 \choose k} 单调递增。

因此可以先枚举红色再枚举蓝色，即先枚举将 i 从 2 开始枚举，再将 j 从 i 开始枚举，直到 {j \choose j-i+1}>n，具体可用 {j\choose j-i+1}=\frac{j}{j-i+1}{j-1\choose j-i} 递推计算。

这种方法快到飞起，n=5\times 10^7 时也能在一秒内通过。

参考程序：

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+10;
int f[N],vis[9];
signed main() {
    int n;
    cin>>n;
    for(int i=2;i<=n;++i)
        for(int j=i+1,tmp=i;tmp<=n;++j){
            ++f[tmp];
            tmp=tmp*j/(j-i+1);
        }
    for(int i=2;i<=n;++i)++vis[f[i]];
    for(int i=1;i<=8;++i)if(vis[i])printf("%lld %lld\n",i,vis[i]);
}

时间复杂度

时间复杂度与每个数在杨辉三角中出现的次数有关。

当 n=10^9 时可以达到如下表格：

出现次数 个数
1 1
2 999952655
3 15
4 47321
6 6
8 1
具体而言： 1. 由于对称性，仅有 $2$ 只出现 $1$ 次； 2. 形如 ${p \choose 2}(p> 3)$，$p$ 为质数，出现过 $4$ 次； 3. 形如 $f_{2i+2}f_{2i+3}-1\choose f_{2i}f_{2i+3}-1$，其中 ${f}$ 为斐波那契数列，出现过 $6$ 次； 4. 目前只发现了 $3003$ 出现过 $8$ 次。 事实上有一个 Singmaster 猜想：杨辉三角中数出现的次数是 $O(1)$ 的，即存在一个上界，目前发现出现最多为 $8$ 次，而 Singmaster 认为这个答案是 $10$ 或 $12$。 1971 年，Singmaster 自己证明到了 $O(\log n)$。 1974 年，Abbott，Erdős，Hanson 三个人证明到了 $O(\frac{\log n}{\log\log n})$。 2007 年，Kane 证明到了 $O(\frac{\left(\log n\right)\left(\log\log\log n\right)}{\left(\log\log n\right)^2})$。 若 Singmaster 猜想成立，则该算法的时间复杂度为 $O(n)$。 详细内容可以参考这篇知乎文章[Singmaster猜想——杨辉三角里一个数字最多出现多少次](https://zhuanlan.zhihu.com/p/419302219)