题解：P12876 [蓝桥杯 2025 国 Python A] 杨辉三角
Redroad
·
·
题解
题目传送门：这里
0. 前置知识
你只需要知道组合数公式 \binom{n}{m} =\frac{n!}{m!(n-m)!} 就可以了，非常简单。
学会了？让我们来看一看这道题吧。
1. 思路分析
观察数据范围， n \le 10 ^ 5，乍一看好像暴力无法通过。
然而事实真的如此吗？
至于怎么求这个最小行数？不会？没关系，我也不会求，但是我们可以 break，当我们枚举到的数大于 $n$ 时直接跳出不就行了嘛！
当然，这个思路还可以优化。如果你的注意力惊人，你就会发现：
**杨辉三角形是对称的！**
所以我们只用枚举到对称轴就可以了。
### 2. 实现
好了，思路想好了，可以开始写代码啦！
但是，直觉告诉我们这题不可能这么快结束。不出所料，我们还有一个关键问题没有解决：
**如何求出当前枚举到的项？**
这就要用到我们的前置知识了。
我们现在枚举到了 $\binom{i}{j}$ ，我们希望的是从 $\binom{i}{j-1}$ 中求出当前项，有没有一个递推公式呢？
有的，兄弟，有的。接下来我们来推导一下：
我们知道：
$$ \binom{i}{j} =\frac{i!}{j!(i-j)!}$$
$$ \binom{i}{j-1} =\frac{i!}{(j-1)!(i-j+1)!}$$
我们将两式相除可以得到：
$$\frac{\binom{i}{j}}{\binom{i}{j-1}} =\frac{\frac{i!}{j!(i-j)!}}{\frac{i!}{(j-1)!(i-j+1)!}}$$
把 $i!$ 约掉：
$$\frac{\binom{i}{j}}{\binom{i}{j-1}}=\frac{(j-1)!(i-j+1)!}{j!(i-j)!}$$
回忆一下阶乘的定义，$n!$ 就是从 $1$ 乘到 $n$，所以原式中 $(j-1)!$ 和 $j!$ 可以约掉，剩一个 $j$，后面的同理。于是我们就可以得出：
$$\frac{\binom{i}{j}}{\binom{i}{j-1}}=\frac{i-j+1}{j}$$
我们要找的是 $\binom{i}{j}$，于是我们十字交叉相乘可得：
$$\binom{i}{j}\times j=\binom{i}{j-1}\times (i-j+1)$$
移项，终于得到了我们梦寐以求的公式：
$$\binom{i}{j}=\binom{i}{j-1}\times (i-j+1)/j$$
到这一步，问题就解决的差不多了。
### 3. AC代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int rma;
int ans[100005];//每个数的出现次数
int sum[100005];//答案序列
int ma;//出现次数的最大值
signed main()
{
cin>>n;
for(int i=2;i<=n;i++){
int c=1;
for(int j=1;j<=i/2;j++){
c=c*(i-j+1)/j;//推导出来的公式，递推求组合数
if(c>n) break;
if(j==i-j){//判断是否是对称轴上的数
//由于我们是按照组合数定义的，所以行号从0开始，第偶数行才有对称轴
ans[c]++;
}else{
ans[c]+=2;
}
}
}
for(int i=2;i<=n;i++){
sum[ans[i]]++;
ma=max(ma,ans[i]);//方便等会找输出的上界
}
for(int i=1;i<=ma;i++){
if(sum[i]) cout<<i<<' '<<sum[i]<<endl;
}
return 0;
}
```
### 4. 小细节
有些童鞋（比如我）可能会这么想：杨辉三角的第一列永远是 $1$，那我为什么不直接从 $j=2$ 开始枚举呢？
于是喜提 $0$ 分...
我们的递推公式是从 $1$ 开始推导的，如果 $j$ 从 $2$ 开始枚举，就会导致组合数计算错误，当然无法通过，所以还是老老实实从 $1$ 开始吧。
那为什么 $i$ 可以从 $2$ 开始枚举呢？因为我们每一层的组合数都是从 $1$ 开始的，所以起始的行数并不重要，由于第 $0$ 行和第 $1$ 行都没有大于 $1$ 的数字，所以可以直接从 $i=2$ 开始枚举。