Problem outline
Let f(x) be the number of times a positive integer x appears in Pascal’s triangle.
Given n, the task is to enumerate every integer x with 2 <= x <= n, then count how many distinct values of f(x) occur, and how many numbers share each frequency.
In other words, after computing f(2), f(3), ..., f(n), we need to group numbers by their occurrence count.
Rewriting Pascal’s triangle as a grid DP
Start from the usual Pascal triangle, where numbers on the two edges are 1, and every interior value is the sum of the two numbers above it.
Marking numbers on the symmetry axis with *, we get:
*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
Now rotate it 45 degrees counterclockwise. The same values can be viewed as another table:
*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
Use coordinates with the upper-left corner as (0,0), positive x to the right, and positive y downward.
For example:
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)
Under this representation:
- the entire first row (
y = 0) is1 - the entire first column (
x = 0) is1 - every other cell satisfies
[ \text{M}[x][y] = \text{M}[x-1][y] + \text{M}[x][y-1] ]
So the problem becomes: generate all values <= n in this grid, count how many times each number appears, and finally group numbers by that count.
Straightforward DP
The most direct method is to build an n x n table and fill it by recurrence.
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)
A couple of details justify the loop bounds:
- In the rotated view, the first two numbers of row
y = 0are1, 1; of rowy = 1they are1, 2; ...; of rowy = n - 1they are1, n. By the recurrence, the next row begins with1, n + 1, which is already greater thann. So there is no need to process beyond thenth row. - The task only asks about numbers
>= 2. Since both coordinates start from1in the DP loops, the value1is never counted, so no extra filter is needed.
This version gets only partial credit: 50 points, with the remaining cases ending in MLE.
Optimization 1: rolling array
The recurrence only needs the previous row and the current row, so the full matrix can be compressed to two rows.
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)
This reduces memory enough to move past MLE, but it still times out on the harder tests: 60 points, with the rest TLE.
Optimization 2: use symmetry
The key observation is that Pascal’s triangle is symmetric. On the symmetry axis, the two “shoulder” values are equal.
Looking again at the rotated form:
*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
The starred numbers on the diagonal not only satisfy
[ \text{M}[x][y] = \text{M}[x-1][y] + \text{M}[x][y-1] ]
but also, because the two contributors are equal there,
[ \text{M}[x][y] = \text{M}[x][y-1] \times 2 ]
So for row y = i with i >= 1, we do not need to recompute the first i positions. We can jump directly to the diagonal value M[i][i], then continue the recurrence from there.
That leads to the full piecewise rule:
[ \text{M}[x][y] = \begin{cases} 1 \quad (x = 0 \text{ or } 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} ]
There is one more advantage: for off-axis values, every number appears twice by symmetry, so each such value contributes 2 to the occurrence count instead of 1.
Accepted solution
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)
What makes this work
The core ideas are fairly compact:
-
Pascal triangle recurrence - After rotating the structure into a grid, each value can be generated by dynamic programming.
-
Rolling array compression - Only the previous row is needed, so the space cost drops from
O(n^2)toO(n). -
Symmetry of Pascal’s triangle - Diagonal values can be computed by doubling. - Non-diagonal values contribute twice to the frequency count. - Once a value on the diagonal exceeds
n, everything to its right and everything in later rows must also exceedn, so the loop can terminate immediately.
The main difficulty in this problem is not the recurrence itself, but noticing how much redundant work can be removed once the symmetry is brought into the DP.