题目链接：P12876 [蓝桥杯 2025 国 Python A] 杨辉三角 – 洛谷
首发：题解：P12876 [蓝桥杯 2025 国 Python A] 杨辉三角 – 洛谷专栏
附言：第一次参加蓝桥杯国赛，希望不要打铁。第一次在洛谷提交题解，希望能过审。
题目简述
记 f(x) 为正整数 x 在杨辉三角中出现的次数。题目要求：
给定 n，枚举 2 \leq x \leq n，统计不同的 f(x) 各自出现了多少次。
等价递推变形
观察杨辉三角（数字前标注 * 说明该数字在对称轴上），如下图所示（记为图 A）：
*1
1 1
1 *2 1
1 3 3 1
1 4 *6 4 1
1 5 10 10 5 1
1 6 15 *20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 *70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 *252 210 120 45 10 1
将杨辉三角逆时针旋转 45^\circ，得到图 B：
*1 1 1 1 1 1 1 1 1 1
1 *2 3 4 5 6 7 8 9 10
1 3 *6 10 15 21 28 36 45 55
1 4 10 *20 35 56 84 120 165 220
坐标规定：左上角为 (0,0)，向右为 x 轴正方向，向下为 y 轴正方向。
例如：
1(0,0) 1(1,0) 1(2,0)
1(0,1) 2(1,1) 3(2,1)
1(0,2) 3(1,1) 4(2,2)
杨辉三角每一行开头和结尾的数是 1；每一行中间的数字等于其“肩”上两数的和。
转换成图 B 的形式就是第 1 行（y=0 行）和第 1 列（x=0 列）的数都是 1；坐标为 (x,y)（x \neq 0 且 y \neq 0）的数等于 (x-1,y) 和 (x,y-1) 的和。
即
题目给定 n，要求我们统计 2 \leq x \leq n 的整数 x 在杨辉三角出现的次数 f(x)，并统计不同 f(x) 值的出现次数。只需递推并统计即可。
暴力做法
from collections import defaultdict
n = int(input())
M = [[1] * n for _ in range(n)]
# count[x] 表示 x 在杨辉三角出现的次数
# 即 f(x) = count[x]
count = defaultdict(int)
for i in range(1, n):
for j in range(1, n):
num = M[i][j] = M[i - 1][j] + M[i][j - 1]
if num > n:
break
else:
count[num] += 1
# stat[n] 表示有多少个 x 使 f(x) = n
stat = defaultdict(int)
for x in range(2, n + 1):
stat[count[x]] += 1
# 字典自动根据 k 排序，无需额外排序后输出
for k, v in stat.items():
print(k, v)
注释：
- 第 1 行（y=0 行）开头两个数字为 1 和 1，到第 n 行（y=n-1 行）开头两个数字为 1 和 n，根据递推公式下一行前两个数字（坐标为 [0,n] 和 [1,n]）为 1 和 n+1，必定大于 n。因此只需遍历到第 n 行即可。
- 题目要求只统计大于等于 2 的数，遍历 x, y 坐标都是从 1 开始，因此不会遍历到 1，也就是无需对
num进行额外判断是否大于 1。
结果： 50 分，剩下的点 MLE。
优化一：滚动数组
递推公式只需上一行，矩阵可压缩为两行：
from collections import defaultdict
n = int(input())
M = [[1] * n for _ in range(2)]
# count[x] 表示 x 在杨辉三角出现的次数
# 即题目 f(x) = count[x]
count = defaultdict(int)
for _ in range(1, n):
for j in range(1, n):
num = M[1][j] = M[0][j] + M[1][j - 1]
if num > n:
break
else:
count[num] += 1
M[0] = M[1].copy()
# stat[n] 表示有多少个 x 使 f(x) = n
stat = defaultdict(int)
for x in range(2, n + 1):
stat[count[x]] += 1
# 字典自动根据 k 排序，无需额外排序后输出
for k, v in stat.items():
print(k, v)
结果： 60 分，剩下的点 TLE。
优化二：利用对称性
考虑到杨辉三角是个对称结构，观察图 A 可知，对称轴上的数“肩”上两数是相同的。
再次观察图 B（数字前标注 * 说明这个数字在对称轴上）：
*1 1 1 1 1 1 1 1 1 1
1 *2 3 4 5 6 7 8 9 10
1 3 *6 10 15 21 28 36 45 55
1 4 10 *20 35 56 84 120 165 220
可以发现，对称轴上的数（数字前标注 * 的数）不仅满足递推公式 \text{M}[x][y] = \text{M}[x-1][y] + \text{M}[x][y-1] ，还满足 \text{M}[x][y] = \text{M}[x][y-1] \times 2 。
也就是说，在 y = i (i \ge 1) 的行，可以直接从 \text{M}[i][i] 开始递推，无需计算前 i 个数。
因此，完整的递推公式为：
1 \quad (x = 0 \text{ 或 } y = 0) \\
\text{M}[x][y-1] \times 2 \quad (x > 1,\, y > 1,\, x = y) \\
\text{M}[x-1][y] + \text{M}[x][y-1] \quad (x > 1,\, y > 1,\, x \neq y)
\end{cases}
最终 AC 代码如下：
from collections import defaultdict
n = int(input())
M = [[1] * n for _ in range(2)]
# count[x] 表示 x 在杨辉三角出现的次数
# 即题目 f(x) = count[x]
count = defaultdict(int)
for i in range(1, n):
num = M[1][i] = M[0][i] * 2
if num > n:
break # 对称轴上的都比 n 大了，这一行后续的数必定比 n 更大，下一行的也必定比 n 更大，因此直接结束
else:
count[num] += 1 # 此处 num 为对称轴上的数
for j in range(i + 1, n):
num = M[1][j] = M[1][j - 1] + M[0][j]
if num > n:
break # num 比 n 大了，这一行后面的也必定比 n 大，结束这一行
else:
count[num] += 2 # 此处 num 为非对称轴上的数
M[0] = M[1].copy()
# stat[n] 表示有多少个 x 使 f(x) = n
stat = defaultdict(int)
for x in range(2, n + 1):
stat[count[x]] += 1
# 字典自动根据 k 排序，无需额外排序后输出
for k, v in stat.items():
print(k, v)
总结
本题关键知识点：
- 杨辉三角的递推公式与对称性。
- 理解杨辉三角的生成方式，发现并利用其对称结构进行优化。
- 动态规划与滚动数组优化。
- 用动态规划思想递推出所有可能的数，并通过滚动数组降低空间复杂度。
感谢阅读。鄙人不才，欢迎在评论区指正！