题解：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) 的和。

即

\text{M}[x][y] = \text{M}[x-1][y] + \text{M}[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)

注释：

结果： 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)

总结

本题关键知识点：

  1. 杨辉三角的递推公式与对称性。
    • 理解杨辉三角的生成方式，发现并利用其对称结构进行优化。
  2. 动态规划与滚动数组优化。
    • 用动态规划思想递推出所有可能的数，并通过滚动数组降低空间复杂度。

第一次写投稿题解，欢迎指正！