一共n级台阶，每次走可以3k+1步（1,4,7,...），问总方案数（对100003取模）。
例如n=5，有下三种方案：
1,1,1,1,11,44,1
题解¶
递归¶
递归的想法非常简单，考虑最后一次走了多少步即可： $$ f(n) = f(n-1)+f(n-4)+f(n-7)+\cdots $$
from functools import cache
# 如果不用cache的话，非常慢～
@cache
def f(n):
if n <= 3:
return 1
else:
return sum(f(n - i) for i in range(1, n + 1, 3)) % 100003
f(100)
66385
默认情况下，最大递归深度是1000，如果要计算f(2000)会抛出错误：
try:
f(2000)
except Exception as e:
print(repr(e))
RecursionError('maximum recursion depth exceeded')
import sys
# 手动设置最大递归栈深度，来进行更深的递归
sys.setrecursionlimit(10**9)
f(2000)
49615
并且由于cache的使用，我们可以继续递归到更深。
直接运行f(10000)依然会触发RecursionError：
try:
f(10000)
except Exception as e:
print(repr(e))
RecursionError('maximum recursion depth exceeded')
但是我们可以一千一千计算过去，就不会触发了：
f(3000), f(4000), f(5000), f(6000), f(7000), f(8000), f(9000), f(10000)
(49640, 62552, 8463, 62667, 36907, 81995, 86926, 30763)
递归递推¶
思路和递归完全一样。使用哈希表代替了递归，可以避开递归栈过深的报错，从而求更大规模的问题：
def f(n):
d = {0: 1, 1: 1, 2: 1, 3: 1} # 字典存放--台阶数：方案数
if n < 4:
return 1
else:
for i in range(4, n + 1): # 求得{3k+1}数列中不大于i的最大项为m
if i % 3 == 0:
m = i - 2
elif i % 3 == 1:
m = i
else:
m = i - 1
d[i] = (
sum([d[i - j] for j in range(1, m + 3, 3)]) % 100003
) # 同样的递推关系，用字典来操作
return d[n] # 返回字典中键n的值
f(100)
66385
%timeit f(10000)
995 ms ± 6.91 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
组合数学¶
$$ \sum_{i=1}^m (3k_i+1) = n $$
如同上式，我们假设m步走完了n级台阶，那么m = n,n-3,n-6,...，也就是说n-m一定是3的倍数：
$$ \sum_i k_i = (n-m)/3 $$
这是一个自然数（$k_i\ge 0$）的不定方程，使用插板法立即可以得到解的个数：
$$ \begin{pmatrix} m-1\\ \frac{n+2m}{3}-1 \end{pmatrix} $$
所以
$$ f(n) = \sum_m \begin{pmatrix} m-1\\ \frac{n+2m}{3}-1 \end{pmatrix} $$
插板法
首先把问题转化为正整数的不定方程： $$ \sum_i(k_i +1) = \frac{n+2m}{3} $$ 于是问题可以建模为$\frac{n+2m}{3}$个苹果，分成$m$份（每一份至少有一个苹果）的问题。我们可以把苹果排成一列，然后用$m-1$个隔板就可以完成苹果的划分。例如两个隔板把六个苹果分成三份：`1|11|111`。注意我们只能在苹果之间选择位置插入隔板，所以只有$\frac{n+2m}{3}-1$个位置可以选择。于是最终的答案是： $$ \begin{pmatrix} m-1\\ \frac{n+2m}{3}-1 \end{pmatrix} $$from math import comb
def f(n):
return sum(comb((n + 2 * m) // 3 - 1, m - 1) for m in range(n, 0, -3)) % 100003
f(10)
19
f(100)
66385
%timeit f(10000)
984 ms ± 6.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
线性递推¶
不难发现： $$ \begin{aligned} f(n) &= f(n-1)+f(n-4)+f(n-7)...\\ f(n-1) &= f(n-2)+f(n-5)+f(n-8)...\\ f(n-2) &= f(n-3)+f(n-6)+f(n-9)...\\ f(n-3) &= f(n-4)+f(n-7)+f(n-10)... \end{aligned} $$
所以 $$ f(n) = f(n-1)+f(n-3) $$
这是一个线性递推数列，可以在常数空间复杂度和线性时间复杂度求解：
def f(n):
a, b, c = 1, 1, 1
if n <= 3:
return 1
else:
for _ in range(n - 3):
a, b, c = b, c, (c + a) % 100003
return c
f(10)
19
f(100)
66385
%timeit f(10000)
568 μs ± 8.9 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
快速幂¶
齐次的线性递推方程，可以用矩阵快速幂的方法在对数时间内求解：
$$ \begin{bmatrix} f(n)\\f(n-1)\\f(n-2) \end{bmatrix} = \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}\begin{bmatrix} f(n-1)\\f(n-2)\\f(n-3) \end{bmatrix} = \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}^{n-3}\begin{bmatrix} f(3)\\f(2)\\f(1) \end{bmatrix} $$
MOD = 100003
def mul(a, b):
"""a,b都是nxn的矩阵"""
n = len(a)
return [
[sum(a[i][k] * b[k][j] for k in range(n)) % MOD for j in range(n)] for i in range(n)
]
def qpow(m, p):
n = len(m)
res = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
while p:
if p&1:
res = mul(res, m)
p >>= 1
m = mul(m, m)
return res
def f(n):
m = qpow([[1,0,1],[1,0,0],[0,1,0]], n-3)
return sum(m[0]) % MOD
f(10)
19
%timeit f(10000)
114 μs ± 1.39 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
创建日期: 2025-08-06 16:19:55
广告
人要恰饭的嘛🤑🤑