题解：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

时也能在一秒内通过。

参考程序：

CPP

12345678910111213141516#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

n=10^9

内，大部分出现了

2

次，最多出现

8

次。

具体而言：

由于对称性，仅有 $2$ 只出现 $1$ 次；
形如 ${p \choose 2}(p> 3)$ ， $p$ 为质数，出现过 $4$ 次；
形如 $f_{2i+2}f_{2i+3}-1\choose f_{2i}f_{2i+3}-1$ ，其中 ${f}$ 为斐波那契数列，出现过 $6$ 次；
目前只发现了 $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猜想——杨辉三角里一个数字最多出现多少次

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

文章操作

时间复杂度

相关推荐

评论

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