第 85 章　基础数学与递推¶

配套例题：BISHI62 斐波那契数列、BISHI131 数楼梯、BISHI63 计算阶乘、 BISHI59 阶乘末尾非零数字、BISHI60 大水题、BISHI13 九倍平方数、 BISHI61 小q的数列、BISHI72 中位数之和来源：S3 day6 fib.cpp（递推与矩阵加速）；S3 day9《在数学花园里闲逛》前置：81-快速幂与逆元、84-组合数学、22-高精度与大整数

这一章收的是「看起来最简单、实际最容易挂」的一类题：数列求和、斐波那契、阶乘、数位、中位数。它们的算法都是三行，坑全在别处——

表面	真正的考点
「求 \(F_k \bmod p\)」	每一步都要取模，不能算完再取（大整数退化成 \(O(k^2)\)）
「\(T\) 组询问 \(n! \bmod p\)」	预处理一次，不是每组从头乘（\(O(Tn)\) vs \(O(n+T)\)）
「反复求数位和」	数根的闭式公式，以及 \(9 \mid n\) 时答案是 9 不是 0
「所有子序列的中位数之和」	0/1 数组下求和退化成计数
「找出这个数列的第 \(n\) 项」	打表 + 差分 + 猜通项，而不是硬推

Python 在这一章有一个独特的优势和一个独特的陷阱：优势是原生大整数，\(10^{18}\) 不用担心溢出（C++ 要小心 long long）；陷阱也是原生大整数——它不会溢出，所以你不会收到任何警告，只会莫名其妙地慢几十倍。

85.1　等差数列与等比数列¶

公式¶

	等差数列	等比数列（\(q \ne 1\)）
通项	\(a_n = a_1 + (n-1)d\)	\(a_n = a_1 q^{\,n-1}\)
前 \(n\) 项和	\(S_n = \dfrac{n(a_1+a_n)}{2} = na_1 + \dfrac{n(n-1)}{2}d\)	\(S_n = a_1\dfrac{q^n-1}{q-1}\)
\(q = 1\) 时	—	\(S_n = na_1\)（公式失效，必须特判）
常用特例	\(1+2+\cdots+n = \dfrac{n(n+1)}{2}\)	\(1+2+4+\cdots+2^{n-1} = 2^n-1\)

三个高频求和式（笔试里出现频率极高，建议背下来）：

\[\sum_{i=1}^{n} i = \frac{n(n+1)}{2}, \qquad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}, \qquad \sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2\]

Python 的三个坑¶

n = 10 ** 18
print(n * (n + 1) / 2)        # ❌ 5e35，浮点，后面十几位全是垃圾
print(n * (n + 1) // 2)       # ✅ 精确整数

⚠️ 坑一：绝不用 /。\(n \ge 2^{53}\) 时 float 已经放不下整数了，而 n(n+1)/2 在 \(n = 10^{18}\) 时是 \(5\times10^{35}\)——错得悄无声息。 整除永远写 //。见 23-浮点与科学计数法。

⚠️ 坑二：模意义下不能直接 // 2。 \(\dfrac{n(n+1)}{2} \bmod p\) 不等于 \(\dfrac{n(n+1) \bmod p}{2}\)。两条正确路线： ① 先在整数里约掉——n 和 n+1 必有一个是偶数，先除再取模： (n // 2) * (n + 1) % p if n % 2 == 0 else n * ((n + 1) // 2) % p； ② 乘 2 的逆元——\(p\) 是奇素数时 \(\text{inv}2 = \dfrac{p+1}{2}\)，直接写 n % p * ((n + 1) % p) % p * ((p + 1) // 2) % p。见 81 章。

Python 里推荐路线①：不需要 \(p\) 是素数，也不需要求逆元。

⚠️ 坑三：等比求和取模时 \(q \equiv 1 \pmod p\) 会让分母变 0。 \(\dfrac{q^n-1}{q-1} \bmod p\) 在 \(q \equiv 1\) 时分母不可逆，公式直接崩。用分治求和绕开，它不需要逆元、不需要 \(p\) 是素数、\(q \equiv 1\) 也照样对：

def geo_sum(q, n, mod):
    """求 1 + q + q^2 + ... + q^(n-1) 对 mod 取模。O(log n)。

    递推关系（S(k) 表示前 k 项和）：
        S(2k)   = S(k) * (1 + q^k)
        S(2k+1) = S(2k) + q^(2k)
    从 n 的二进制高位往低位扫，同时维护 s = S(当前前缀) 和 p = q^(当前前缀)。
    不用逆元，所以 q ≡ 1 (mod mod)、mod 非素数都没问题。
    """
    if n <= 0:
        return 0                             # 空和，避免下面 bin(0) 的退化情形
    s = 0                                    # S(0) = 0
    p = 1                                    # q^0 = 1
    # bin(n) 形如 "0b1011"，切掉前两个字符就得到从高位到低位的二进制串
    for bit in bin(n)[2:]:                   # 高位 -> 低位
        # 已有的前缀 k 翻倍：S(2k) = S(k) + q^k * S(k) = S(k) * (1 + q^k)
        s = s * (1 + p) % mod                # k -> 2k
        p = p * p % mod                      # q^k 同步平方成 q^(2k)
        if bit == "1":                        # 2k -> 2k+1
            s = (s + p) % mod                # 补上第 2k 项，它正是当前的 q^(2k)
            p = p * q % mod                  # 指数再 +1
    return s

85.2　斐波那契数列¶

下标约定：读题第一件事¶

约定	序列	出现场合
\(F_0=0,\ F_1=1\)	\(0,1,1,2,3,5,8,\dots\)	数学文献、`gcd` 性质、快速倍增公式
\(F_1=F_2=1\)	\(1,1,2,3,5,8,\dots\)	竞赛题面最常见（BISHI62 就是这个）

两种约定给出的 \(F_k\)（\(k \ge 1\)）数值完全一样，但「第 \(n\) 项」的含义差一位，所以必须以题面给的初值为准。

性质表¶

性质	式子	用途
前缀和	\(\sum_{i=1}^{n}F_i = F_{n+2}-1\)	求和题一步化简
平方和	\(\sum_{i=1}^{n}F_i^2 = F_nF_{n+1}\)
加法公式	\(F_{m+n} = F_mF_{n+1} + F_{m-1}F_n\)	快速倍增的来源
倍增公式	\(F_{2k}=F_k(2F_{k+1}-F_k)\)，\(F_{2k+1}=F_k^2+F_{k+1}^2\)	\(O(\log n)\) 求单项
gcd 性质	\(\gcd(F_m,F_n)=F_{\gcd(m,n)}\)	「斐波那契数的公约数」类题
整除性	\(m \mid n \Rightarrow F_m \mid F_n\)	上一条的推论
增长速度	\(F_n \approx \dfrac{\varphi^n}{\sqrt5}\)，\(\varphi=\dfrac{1+\sqrt5}{2}\)	判位数：\(F_n\) 约有 \(0.209n\) 位
Zeckendorf	任意正整数可唯一表示成若干不相邻斐波那契数之和	贪心分解、博弈论
Pisano 周期	\(F_n \bmod m\) 一定是周期数列	见 84.6 鸽巢原理

「\(F_n\) 约有 \(0.209n\) 位」是本章最有用的一条估算： \(\log_{10}\varphi \approx 0.20898\)。于是 \(F_{10^6}\) 有约 20.9 万位—— 这个数字直接决定了下面「为什么必须随时取模」。

三种求法与选型¶

MOD = 1000000007


def fib_linear(k, mod=MOD):
    """线性递推求 F_k（F_1 = F_2 = 1）。O(k)，每步取模。"""
    a, b = 0, 1                              # a = F_0, b = F_1
    # 循环 k-1 次后 b 从 F_1 推到 F_k；k = 1 时不进循环，直接返回 F_1
    for _ in range(k - 1):
        a, b = b, (a + b) % mod              # ★ 元组交换 + 随时取模
    return b


def fib_pair(n, mod=MOD):
    """快速倍增：返回 (F_n, F_{n+1}) mod mod（F_0 = 0, F_1 = 1）。O(log n)。

    F_2k   = F_k * (2*F_{k+1} - F_k)
    F_2k+1 = F_k^2 + F_{k+1}^2
    递归深度只有 log2(n)，n = 1e18 时也才 60 层，不会爆栈。
    比矩阵快速幂少一半乘法，是求「单个 F_n」的最优写法。
    """
    if n == 0:
        return 0, 1                          # 递归边界：(F_0, F_1) = (0, 1)
    a, b = fib_pair(n >> 1, mod)             # a = F_k, b = F_{k+1}
    # 2b - a 可能是负数，先 % mod 拉回 [0, mod)：Python 的 % 对负数返回非负，
    # 所以不必写 C++ 里那句 ((x % m) + m) % m
    c = a * ((b + b - a) % mod) % mod        # F_2k
    d = (a * a + b * b) % mod                # F_2k+1
    # n 的最低位决定这一层要的是 (F_2k, F_2k+1) 还是 (F_2k+1, F_2k+2)，
    # 而 F_2k+2 = F_2k + F_2k+1 = c + d
    if n & 1:
        return d, (c + d) % mod              # n = 2k+1
    return c, d                              # n = 2k

矩阵快速幂的写法是同一件事的另一种包装：

\[\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} \begin{pmatrix}F_1\\F_0\end{pmatrix}\]

它的价值不在斐波那契（快速倍增更快），而在任意线性齐次递推都能套： \(a_n = c_1a_{n-1}+\cdots+c_ka_{n-k}\) 一律可以写成 \(k \times k\) 矩阵的 \(n\) 次幂。完整讨论见 104-DP优化与 45-倍增、81-快速幂与逆元。

方法	复杂度	Python 可行的 \(k\)	什么时候用
递归 + `lru_cache`	\(O(k)\)	\(\le 900\)	❌ 递归深度就是 \(k\)，\(k \ge 1000\) 必 `RecursionError`
线性递推	\(O(k)\)	\(\le 10^7\)	默认选择（BISHI62 的 \(k \le 10^6\)）
快速倍增	\(O(\log k)\)	任意（\(10^{18}\) 也行）	单项、\(k\) 极大
矩阵快速幂	\(O(2^3\log k)\)	任意	递推项数 \(\ge 3\)、带常数项、或要顺便求前缀和
通项公式（Binet）	\(O(1)\)	❌ 不可用	涉及 \(\sqrt5\)，浮点误差在 \(n \ge 80\) 就出错

⚠️ 绝不用 Binet 公式：\(F_n = \dfrac{\varphi^n - \psi^n}{\sqrt5}\) 在数学上精确，在 float 下 \(n = 71\) 就开始出错，\(n = 80\) 已经错得离谱。（模素数下若 5 是二次剩余，可以用「模意义的 \(\sqrt5\)」精确算，但那比快速倍增麻烦得多。）

Python 的核心取舍：为什么必须随时取模¶

# ❌ 先算精确值再取模
a, b = 0, 1
for _ in range(k - 1):
    a, b = b, a + b          # b 会长成 20 万位的大整数
print(b % MOD)

Python 的 int 不会溢出，所以这段代码不报错、结果也对——只是慢得没法看：

\(k\)	随时取模	先算精确值
\(10^5\)	0.010 s	0.084 s
\(10^6\)	0.057 s	6.4 s

（本机实测，CPython 3.9。）

原因：大整数加法是 \(O(\text{位数}/64)\)，而 \(F_i\) 的位数线性增长，总复杂度从 \(O(k)\) 退化成 \(O(k^2/64)\)。每一步 % MOD 把数值钉死在 30 位以内，加法才是真正的常数时间。

这条判据适用于所有「模意义下的递推」：斐波那契、阶乘、组合数、DP 转移，一律「边算边取模」。这是 Python 竞赛里最容易犯、最难自己发现的性能错误—— 因为 C++ 选手会溢出得到错误答案，立刻发现；Python 选手只会 TLE。完整讨论见 22-高精度与大整数。

85.3　阶乘¶

增长速度与 `math.factorial` 的边界¶

\(n!\) 的十进制位数由斯特林公式给出：

\[\log_{10} n! \approx n\log_{10}n - \dfrac{n}{\ln 10} + \dfrac{1}{2}\log_{10}(2\pi n)\]

\(n\)	\(n!\) 的位数	`math.factorial(n)` 本机耗时
20	19	立即（\(20! < 2^{64}\)，C++ 也放得下）
\(10^3\)	2568	立即
\(10^5\)	456574	0.12 s
\(10^6\)	5565709	6.1 s（且占用几十 MB）

判据：math.factorial 只在 \(n \le 10^5\) 且真的需要精确值时可用（比如高精度输出 \(n!\)）。只要题目要求「模 \(p\)」，就一律用递推表，别写 math.factorial(n) % p——那是把 550 万位的数算出来再丢掉。

阶乘取模：预处理表¶

def fact_table(n, mod=1000000007):
    """阶乘表 fact[0..n]，每步取模。O(n)。

    本机实测 n = 1e6 约 0.11 s，而 math.factorial(1e6) 要 6 s。
    """
    fact = [1] * (n + 1)                     # fact[0] = fact[1] = 1，由初值直接给出
    for i in range(2, n + 1):
        fact[i] = fact[i - 1] * i % mod      # 每步取模，数值钉死在 30 位以内
    return fact


def inv_fact_table(fact, mod=1000000007):
    """阶乘逆元表，从最后一项倒推。只做 1 次快速幂，其余是乘法。O(n)。

    依据 inv_fact[i-1] = inv_fact[i] * i：
        1/(i-1)! = 1/i! * i
    """
    n = len(fact) - 1
    inv = [1] * (n + 1)
    # 只有表尾这一项花一次快速幂；mod 是素数时 x^(mod-2) 就是 x 的逆元
    inv[n] = pow(fact[n], mod - 2, mod)      # 费马小定理，mod 必须是素数
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % mod        # 倒着推：n 次乘法换掉 n 次快速幂
    return inv

「多组询问 + 同一上界」= 预处理。这是 BISHI63 的全部考点： \(T\) 组各自从头乘一遍是 \(O(Tn) = 10^9\) 次乘法取模（必死），预处理一次是 \(O(n + T)\)。组合数取模也是同一套表，见 84.4。

勒让德公式：\(n!\) 里有多少个质因子 \(p\)¶

\[v_p(n!) = \sum_{i \ge 1} \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots\]

推导很直观：\(1..n\) 里 \(p\) 的倍数有 \(\lfloor n/p \rfloor\) 个（每个至少贡献一个 \(p\)）， \(p^2\) 的倍数有 \(\lfloor n/p^2 \rfloor\) 个（每个再多贡献一个）……层层累加。

def legendre(n, p):
    """v_p(n!)：n! 的质因数分解里 p 的指数。O(log_p n)。"""
    c = 0
    q = p
    # q > n 时 n // q 已经是 0，再累加没有意义，所以循环只有 log_p(n) 层
    while q <= n:
        c += n // q                          # 1..n 里 q 的倍数各再多贡献一个 p
        q *= p                               # p, p^2, p^3, ...
    return c


def trailing_zeros_factorial(n):
    """n! 末尾有多少个 0 = min(v_2, v_5) = v_5（因为 2 的因子总是更多）。"""
    return legendre(n, 5)

用途	式子
\(n!\) 末尾 0 的个数	\(v_5(n!)\)
\(n!\) 能被 \(p^k\) 整除吗	\(v_p(n!) \ge k\)
组合数 \(\binom{n}{m}\) 里 \(p\) 的指数	\(v_p(n!) - v_p(m!) - v_p((n-m)!)\)（Kummer 定理）
阶乘末尾第一个非零位	先除掉 \(10^{v_5}\)，再模 10（BISHI59）

⚠️ 常见错法：把「末尾 0 的个数」写成 \(\lfloor n/5 \rfloor\) 或 \(\lfloor n/4 \rfloor\)。前者漏掉了 25、125 的额外贡献（\(n = 25\) 时真值是 6 而不是 5），后者是把等比和 \(\frac{n/5}{1-1/5}\) 当成了精确值——近似值不是答案。 while q <= n 的循环只有 \(\log_5 n \approx 10\) 层，没有任何理由偷懒。

威尔逊定理（\((p-1)! \equiv -1 \pmod p\)）见 80.8。

85.4　数位处理¶

三种拆位方式¶

方式	写法	顺序	什么时候用
`str`	`list(map(int, str(n)))`	高位 → 低位	`n` 是 `int` 且要按位顺序处理
`divmod`	`while n: n, d = divmod(n, 10)`	低位 → 高位	只需低位优先；不想建列表
`bytes`	`sum(s) - 48 * len(s)`	—	输入本身就是超长数字串

def digits_high_to_low(n):
    """高位到低位的数位列表。n = 0 时返回 [0]。"""
    return [int(c) for c in str(n)]


def digits_low_to_high(n):
    """低位到高位的数位列表，不经过字符串。"""
    if n == 0:
        return [0]                           # 循环条件是 `while n`，0 进不去，要特判
    out = []
    while n:
        n, d = divmod(n, 10)                 # ★ divmod 一次拿到商和余
        out.append(d)                        # 先出来的是最低位，所以结果是低位在前
    return out


def digit_sum_bytes(s):
    """超长数字串（bytes）的数位和。O(len)，全在 C 层。

    bytes 迭代出的是字节值，b'0' = 48，所以整体求和后减掉 48 * 长度。
    """
    return sum(s) - 48 * len(s)

⚠️ 超长数字串千万不要 int(s)。 int(str) 在 CPython 里是 \(O(d^2)\) 的（\(d\) 是位数）：\(d = 10^5\) 时约 0.03 秒， \(d = 10^6\) 时就要 3 秒以上。而且 Python 3.11 起 int() 对超过 4300 位的串直接抛 ValueError（需要 sys.set_int_max_str_digits 放开）—— 判题机版本不确定时，这是个致命的兼容性问题。 只要问的是「数位和 / 模 9 / 模 11 / 各位统计」，就在字节串上做，永远不要转 int。 sum(s) - 48*len(s) 的实测速度是 sum(map(int, s)) 的 10 倍（\(10^5\) 位：0.4 ms vs 4.3 ms）。

数位和与整除判定¶

十进制下 \(10 \equiv 1 \pmod 9\)，所以 \(10^k \equiv 1 \pmod 9\)，于是

\[n \equiv (\text{各位数字之和}) \pmod 9\]

同理 \(10 \equiv -1 \pmod{11}\) 给出交替和：

判定	依据
\(3 \mid n\) / \(9 \mid n\)	数位和被 3 / 9 整除
\(11 \mid n\)	交替和（从低位起 \(d_0-d_1+d_2-\cdots\)）被 11 整除
\(2^k \mid n\)	只看末 \(k\) 位
\(5^k \mid n\)	只看末 \(k\) 位
\(7 \mid n\) / \(13 \mid n\)	没有好用的数位判据，直接取模

数根（digital root）¶

反复求数位和直到只剩一位，得到的就是数根。

因为每次求数位和都不改变模 9 的值，而结果最终稳定在 \(1..9\)（\(n \ge 1\)）：

\[\mathrm{dr}(n) = 1 + (n-1) \bmod 9 \qquad (n \ge 1),\qquad \mathrm{dr}(0)=0\]

def digital_root(n):
    """数根。O(1)。注意 9 的倍数答案是 9 而不是 0。"""
    return 0 if n == 0 else 1 + (n - 1) % 9

⚠️ n % 9 是错的：它会把 9、18、27 全算成 0。偏移写法 1 + (n-1) % 9 才对。这是 BISHI60 的唯一考点。

「数位」不只是十进制¶

BISHI61 的递推 \(f(x)=f(\lfloor x/2\rfloor)+f(x \bmod 2)\) 本质是二进制数位和，也就是 popcount。二进制拆位的写法：

def popcount(x):
    """x 的二进制里 1 的个数。

    Python 3.10+ 有 int.bit_count()，但 3.9 没有，判题机版本不确定时
    统一用 bin(x).count("1")：字符串构造 + count 都在 C 层，比逐位移位快得多。
    """
    return bin(x).count("1")

⚠️ int.bit_count() 是 Python 3.10 才加的。牛客的 Python 版本不保证，写了就是 AttributeError。同类禁用清单见 C-Python竞赛避坑清单。逐位 while x: c += x & 1; x >>= 1 是 \(O(\log x)\) 次 Python 层迭代，在 \(T = 5\times10^5\) 组询问下会慢好几倍——bin().count() 把这 60 位下沉到 C 层。

数位构造类问题¶

题型	套路
区间内的回文数 / 对称数	枚举前一半（见 72.5）
数位重排后的最大/最小值	排序数位；最小值要把首位的 0 换掉
「把某些数位替换成别的」能否被 9 整除	只看数位和的增量，增量模 9 有周期 → 枚举常数次（BISHI13）
统计区间内数位满足某性质的数的个数	数位 DP（按位从高到低 + 「是否贴着上界」状态）

85.5　中位数的性质¶

定义¶

长度 \(n\) 的有序数组 \(a_1 \le \cdots \le a_n\)：

\(n\)	中位数
奇数	第 \(\dfrac{n+1}{2}\) 个，即 `a[n // 2]`（0-indexed）
偶数	通常取 \(\dfrac{a_{n/2}+a_{n/2+1}}{2}\)，但竞赛里常约定取第 \(n/2\) 或第 \(n/2+1\) 个

⚠️ 偶数长度的中位数定义必须以题面为准。有的题要平均值（可能是 .5），有的题明确说「第 \(\lceil n/2 \rceil\) 个」。BISHI72 直接限定 \(k\) 为奇数，就是为了绕开这个歧义。

性质一：绝对值和的最小点¶

\(f(x) = \sum_{i=1}^{n} |a_i - x|\) 在 \(x\) 取中位数时最小。

证明（配对剥皮法）：把最小和最大配成一对，

\[|a_1-x| + |a_n-x| \ge a_n - a_1\]

等号当且仅当 \(x \in [a_1, a_n]\)。再对 \((a_2, a_{n-1})\) 做同样的事，要求 \(x \in [a_2, a_{n-1}]\)……一层层剥下去，所有约束的交集是最中间的那个区间：

\(n\) 为奇数：交集缩成一个点 \(a_{(n+1)/2}\)；
\(n\) 为偶数：交集是 \([a_{n/2}, a_{n/2+1}]\)，区间里任意一点都最优（包括两个端点）。

于是有一个很实用的推论：偶数长度时不必纠结取哪个，取 a[n//2] 就行。

对比一下平方和，能看清「中位数 vs 平均数」的分工：

目标	最优点
\(\sum \\|a_i - x\\|\) 最小	中位数
\(\sum (a_i - x)^2\) 最小	平均数
\(\max \\|a_i - x\\|\) 最小	\(\dfrac{\min + \max}{2}\)（中点）

经典模型¶

题型	转化
数轴上 \(n\) 个村庄建一个仓库，总运距最小	建在中位数处
每次操作把某个数 \(\pm1\)，把全部数变成相等的最小操作数	\(\sum\\|a_i - \text{mid}\\|\)
把数组变成严格递增（每次 \(\pm1\)）的最小代价	先令 \(b_i = a_i - i\)，再对 \(b\) 求 \(\sum\\|b_i-\text{mid}\\|\)
二维网格上的曼哈顿距离和最小	\(x\)、\(y\) 独立各取中位数
带权版本（村庄有人口 \(w_i\)）	带权中位数：累加权重超过总权一半的位置

「减去 \(i\)」这一步是全表最值钱的技巧：要求 \(b\) 严格递增等价于 \(a_i - i\) 单调不减，于是「严格递增」的约束被一次平移消掉，问题退化成「变成相等」。类似的「先做一次线性变换再套已知模型」的手法在贪心题里反复出现，见 47-贪心。

性质二：0/1 数组的中位数只能是 0 或 1¶

这是 BISHI72 的全部技巧：

值域只有 \(\{0,1\}\) 时，「中位数之和」= 「中位数为 1 的子序列个数」。 求和退化成计数，于是可以用组合数一次算完。

而「长度 \(k\)（奇数）的子序列的中位数是 1」等价于「它含有至少 \(h = \dfrac{k+1}{2}\) 个 1」。

\[\text{答案} = \sum_{j=h}^{\min(k,\,c_1)} \binom{c_1}{j}\binom{c_0}{k-j}\]

其中 \(c_1\) 是 1 的个数，\(c_0 = n - c_1\)。

「值域很小 ⟹ 求和变计数」是个通用降维手法：只要被求和的量只有 \(O(1)\) 种取值，就把 \(\sum\) 拆成 \(\sum_{v} v \cdot (\text{取值为 } v \text{ 的方案数})\)。 0/1 情形下更省：只有 \(v=1\) 那一项非零。见 84.7 容斥原理。

求中位数的四种方式¶

方式	复杂度	Python 评价
`sorted(a)[n // 2]`	\(O(n\log n)\)	✅ 默认答案：Timsort 在 C 层，\(10^6\) 个数 0.19 s
`statistics.median`	\(O(n\log n)\)	⚠️ 偶数时返回 `float`，且慢；竞赛别用
快速选择（nth_element）	期望 \(O(n)\)	❌ 纯 Python 循环，比 `sorted` 慢好几倍
对顶堆（动态中位数）	每次 \(O(\log n)\)	✅ 数据流式到来时唯一选择，见 35-优先队列与堆

Python 的反直觉结论：理论上 \(O(n)\) 的快速选择，在 CPython 里比 \(O(n\log n)\) 的 sorted 慢。原因是 sorted 的整个比较循环在 C 层，而快速选择的分区循环在 Python 层—— \(\log n \approx 20\) 的因子远小于「Python 层 vs C 层」的 30–50 倍常数差。这是 21-复杂度与Python性能的典型案例。

85.6　递推式的求解思路¶

竞赛里遇到「求这个数列的第 \(n\) 项」时，几乎从不需要真的解出通项—— 只要能写出递推式并判断规模，就已经能做题了。但当 \(n\) 大到不能递推时，就必须走下面这条流水线。

四步流水线¶

① 打表        小规模暴力/DFS 算出前 10~15 项
     ↓
② 差分验证    做一阶、二阶、三阶差分，看哪一层变成常数
     ↓
③ 猜通项      按差分的层数/比值的形态套模板
     ↓
④ 数学归纳    用递推式验证猜出的通项，得到证明

① 打表：先有数据再有结论¶

# [片段] 打表：任何构造/计数题的第一步
def brute(n):
    """小规模暴力。写得慢没关系，正确最重要。"""
    ...


for n in range(1, 16):
    print(n, brute(n))

打表是构造题和递推题的通用起手式，见 48-构造。

② 差分验证：判断是不是多项式¶

判据：若数列的 \(k\) 阶差分是常数，则它是 \(n\) 的 \(k\) 次多项式。

a:      1   4   9  16  25  36        （猜：n^2）
一阶:     3   5   7   9  11
二阶:       2   2   2   2            ← 二阶常数 ⇒ 二次多项式 ✓

a:      1   2   4   8  16  32        （猜：2^(n-1)）
一阶:     1   2   4   8  16
二阶:       1   2   4   8            ← 差分永远不变常数 ⇒ 不是多项式，是指数型

def diff_table(a, levels=4):
    """打印前 levels 阶差分，用来判断数列的形态。"""
    cur = list(a)                            # 拷贝一份，不动调用方的数据
    print("a   :", cur)
    for k in range(1, levels + 1):
        # 每做一次差分长度减 1，所以下标只走到 len(cur) - 2
        cur = [cur[i + 1] - cur[i] for i in range(len(cur) - 1)]
        if not cur:
            break                            # 项数耗尽，再差分没有意义
        print("d%-3d:" % k, cur)

差分表的形态	结论
\(k\) 阶差分恒为常数 \(c\)	\(k\) 次多项式，最高次系数 \(= c / k!\)
一阶差分是常数	等差数列
相邻项比值近似常数 \(q\)	指数型 \(\sim q^n\)
一阶差分本身就是原数列	\(a_n = 2a_{n-1}\)
一阶差分是原数列错位一项	斐波那契型（\(a_n = a_{n-1}+a_{n-2}\)）
都不像	去核对已知数列：卡特兰、贝尔、错位排列（84 章）

③ 猜通项：按递推形式套模板¶

递推形式	通项求法	\(n\) 很大时怎么办
\(a_n = a_{n-1} + d\)	等差公式	\(O(1)\)
\(a_n = q\,a_{n-1}\)	等比公式	快速幂
\(a_n = q\,a_{n-1} + d\)	不动点法（见下）	快速幂
\(a_n = p\,a_{n-1} + q\,a_{n-2}\)	特征方程 \(x^2 = px+q\)	矩阵快速幂
\(a_n = a_{n-1} + f(n)\)，\(f\) 是 \(k\) 次多项式	累加：\(a_n = a_1 + \sum_{i=2}^{n} f(i)\)	求和公式（85.1）
\(a_n = n\,a_{n-1} + g(n)\)	两边除以 \(n!\) 化成可累加形式	—
递推里出现 \(\lfloor n/2 \rfloor\)	按二进制位递归，深度 \(O(\log n)\)（BISHI61）	天然 \(O(\log n)\)

不动点法：解 \(a_n = qa_{n-1}+d\)。设不动点 \(x^* = \dfrac{d}{1-q}\)（\(q \ne 1\)），则 \(a_n - x^* = q(a_{n-1}-x^*)\)，于是 \(\{a_n - x^*\}\) 是等比数列：

\[a_n = q^{\,n-1}(a_1 - x^*) + x^*\]

特征方程法：\(a_n = pa_{n-1}+qa_{n-2}\) 的特征方程是 \(x^2 = px+q\)。两根 \(x_1 \ne x_2\) 时 \(a_n = Ax_1^n + Bx_2^n\)，重根时 \(a_n = (A+Bn)x_1^n\)， \(A, B\) 由两个初值定出。斐波那契就是 \(x^2=x+1\)，根是 \(\varphi\) 和 \(\psi\)，所以有 Binet 公式——也正因为根是无理数，浮点实现不可用（85.2）。

④ 数学归纳：让猜测变成证明¶

猜出 \(a_n = g(n)\) 后，验证：① \(g\) 在初值处正确； ② 假设 \(g(n-1)\)（及 \(g(n-2)\)）正确，代入递推式推出 \(g(n)\) 正确。

为什么这一步不能省：差分表只用了前十几项。「前 15 项吻合但第 16 项就崩」的数列在出题人手里要多少有多少（\(a_n = n^2\) 与 \(a_n = n^2 + \binom{n-1}{15}\) 的前 15 项完全一样）。 打表给出猜测，归纳给出信心。

什么时候完全不需要通项¶

情形	做法
\(n \le 10^7\)	直接线性递推，每步取模。别为难自己（BISHI62、BISHI131）
\(n \le 10^{18}\)，线性齐次	矩阵快速幂 / 快速倍增，\(O(k^3\log n)\)
\(n \le 10^{18}\)，非线性	找周期（模 \(p\) 下状态有限必有循环节，由鸽巢原理保证），见 84.6
递推带 \(\lfloor n/2 \rfloor\) 或 \(n/k\)	递归 + 记忆化，不同的取值只有 \(O(\sqrt n)\) 或 \(O(\log n)\) 个（83-整除分块）

85.7　例题¶

BISHI62 斐波那契数列（简单）¶

\(F_1=F_2=1\)，\(F_i=F_{i-1}+F_{i-2}\)。给定 \(k\ (1 \le k \le 10^6)\)，输出 \(F_k \bmod (10^9+7)\)。题面见 BISHI62 原题（牛客）。题解见 solutions/BISHI62.py（已通过官方样例验证）。

\(k \le 10^6\)，线性递推就够——不需要矩阵快速幂，也不需要快速倍增（那是 \(k\) 到 \(10^{18}\) 时才必要的）。

import sys

MOD = 1000000007

k = int(sys.stdin.buffer.read().split()[0])
a, b = 0, 1                      # a = F_0, b = F_1
# 每转一圈 b 前进一项：循环 k-1 次后 b = F_k。k = 1 时 range(0) 为空，直接得 F_1 = 1
for _ in range(k - 1):
    a, b = b, (a + b) % MOD      # ★ 每步取模，避免退化成大整数加法
# 再模一次是为了 k = 1 的情形：那时 b 还是没进过循环的初值 1
sys.stdout.write(str(b % MOD) + "\n")

复杂度 \(O(k)\)，\(10^6\) 次「加法 + 取模」，本机实测约 0.06 s，时限 2 s，非常宽裕。

三个坑：

下标从 1 开始，\(F_1=F_2=1\)。循环写 range(k - 1) 次、初值 (0, 1)，则 \(k=1\) 时不进循环输出 \(F_1=1\)，\(k=2\) 时进一次输出 1 ✓ —— 用 \(k=1,2\) 手验边界是这类题的必修动作；
取模不能省（85.2 的核心）：不取模时 \(F_{10^6}\) 有 20.9 万位，总耗时从 0.06 s 涨到 6.4 s，慢 100 倍；
不要写递归 + lru_cache：递归深度就是 \(k = 10^6\)， RecursionError 是最好的结果，调大上限后会直接段错误（见 11-函数）。

如果 \(k\) 变成 \(10^{18}\) 呢？ 换 85.2 的 fib_pair（快速倍增），\(O(\log k)\)， 60 层递归。题目从「能不能写循环」变成「知不知道倍增公式」。

BISHI131 数楼梯（简单）¶

每步上 1 阶或 2 阶，求上 \(n\ (n \le 10^5)\) 阶楼梯的走法数，模 998244353。题面见 BISHI131 原题（牛客）。题解见 solutions/BISHI131.py（已通过官方样例验证）。

设 \(f_i\) 为走到第 \(i\) 阶的方案数。最后一步只能是从 \(i-1\) 迈 1 阶或从 \(i-2\) 迈 2 阶，这两类方案互不重叠且覆盖全部情况（这就是 DP 的「不重不漏」），所以

\[f_i = f_{i-1} + f_{i-2}, \qquad f_1 = 1,\ f_2 = 2\]

也就是斐波那契数列错开一位（\(f_n = F_{n+1}\)）。

import sys

MOD = 998244353


def main():
    n = int(sys.stdin.buffer.read().split()[0])
    if n == 1:                               # ★ 特判：否则 f_2 的初值会被误用
        sys.stdout.write("1\n")              # range(-1) 是空的，b 会原样输出 2
        return
    a, b = 1, 2                              # f_1, f_2
    # 循环 n-2 次把 b 从 f_2 推到 f_n；只留两个变量，空间 O(1)
    for _ in range(n - 2):
        a, b = b, (a + b) % MOD              # 每步取模
    sys.stdout.write("%d\n" % b)             # 模数是 998244353，不是 1e9+7


main()

复杂度 \(O(n)\)、\(O(1)\) 空间（滚动两个变量），\(n = 10^5\) 瞬间出结果。

三个坑：

\(n = 1\) 必须特判。初值设的是 \(f_1, f_2\)，\(n=1\) 时循环执行 \(-1\) 次（range(-1) 是空的），会错误输出 \(f_2 = 2\)；
模数是 998244353 而不是 \(10^9+7\)。这两个模数长得很像，抄模板时最容易看错；
问的是「走到顶端」的方案数，\(f_n\) 就是答案，不用再 \(+1\)。

这题同时是 100-DP入门的例题。两章视角不同：100 章讲「怎么定义状态、怎么论证不重不漏」，本章讲「认出它就是斐波那契之后，\(n\) 变大该怎么办」。若把 \(n\) 提到 \(10^{18}\)，答案是矩阵快速幂（104 章）。

BISHI63 计算阶乘（简单）¶

\(T\ (\le 10^3)\) 组询问，每组给 \(n\ (\le 10^6)\)，求 \(n! \bmod (10^9+7)\)。题面见 BISHI63 原题（牛客）。题解见 solutions/BISHI63.py（已通过官方样例验证）。

「多组询问 + 同一个上界」的经典套路：预处理阶乘前缀表，\(O(1)\) 回答。

做法	复杂度	判定
每组从头乘一遍	\(O(T \cdot n) = 10^9\) 次乘法取模	❌ Python 下必死
预处理 `fact[0..maxn]` 一次	\(O(\text{maxn} + T)\)	✅ 约 0.11 s
`math.factorial(n) % MOD`	每组要造一个 550 万位的大整数	❌ 单组就 6 s

还有一个小优化：先把所有询问读进来取 max，只预处理到实际最大的 \(n\)。样例里 \(n=1\)，连表都几乎不用建。

import sys

MOD = 1000000007


def main():
    data = sys.stdin.buffer.read().split()   # 整块读入，先拿到全部询问再决定表长
    t = int(data[0])
    ns = [int(x) for x in data[1:t + 1]]
    m = max(ns) if ns else 0                 # ★ 只建到实际用得到的上界

    fact = [1] * (m + 1)                     # 前缀阶乘表，只建一次
    for i in range(2, m + 1):                # fact[0] = fact[1] = 1 已由初值给出
        fact[i] = fact[i - 1] * i % MOD      # 每步取模

    # 建表 O(m) + 查表 O(T)，取代了「每组从头乘一遍」的 O(T·n)
    sys.stdout.write("\n".join(str(fact[n]) for n in ns) + "\n")


main()

三个坑：

必须先读完全部输入再决定表长，所以用整块读取 + 游标，而不是边读边算（后者只能盲取 \(10^6\) 作为表长，白建一百万项）；
每步取模。\(10^6!\) 精确值有 556 万位，算一次 6 秒、占几十 MB；
输出攒起来一次 join。\(T = 10^3\) 行还不算多，但这是应该形成的肌肉记忆（见 20-输入输出处理）。

扩展：若还要求 \(\binom{n}{m} \bmod p\)，就在同一张表旁边加一张阶乘逆元表（85.3 的 inv_fact_table，只做 1 次快速幂）。见 84.4。

BISHI59 阶乘末尾非零数字（中等）¶

给定 \(n\ (1 \le n \le 10^7)\)，输出 \(n!\) 十进制表示中从右往左第一个非零数字。题面见 BISHI59 原题（牛客）。题解见 solutions/BISHI59.py（已通过官方样例验证）。

这题是本章的压轴：它把「勒让德公式 + 去 5 递归 + 中国剩余定理」串成了一条线。

直接算 \(n!\) 是天方夜谭（\(10^7!\) 约有 \(6.5\times10^7\) 位）。设

\[z = v_5(n!) = \left\lfloor \frac n5\right\rfloor + \left\lfloor \frac n{25}\right\rfloor + \cdots \quad(\text{末尾 0 的个数}),\qquad X = \frac{n!}{10^{\,z}}\]

要求的就是 \(X \bmod 10\)。用中国剩余定理（CRT，由若干个互质模数下的余数唯一还原原数）把模 10 拆成模 2 与模 5（\(10 = 2\times5\) 且二者互质，完整讲解见 114-同余方程组与离散对数）：

\(n \ge 2\) 时 \(v_2(n!) > v_5(n!)\)（2 的倍数比 5 的倍数多得多），所以除掉 \(2^z\) 之后 \(X\) 仍是偶数 ⟹ \(X \equiv 0 \pmod 2\)；
于是只需再求 \(X \bmod 5\)。而 \(X \bmod 5 \in \{1,2,3,4\}\)（5 已经被除干净，不可能是 0），「偶数 + 模 5 余 \(r\)」唯一确定末位：

\(X \bmod 5\)	1	2	3	4
末位	6	2	8	4

求 \(X \bmod 5\)：令 \(F(n)\) = 「\(n!\) 去掉全部因子 5 之后」\(\bmod 5\)。把 \(1..n\) 分成「5 的倍数」与其余两类：

非 5 倍数：每连续 5 个数里有 4 个，乘积 \(1\cdot2\cdot3\cdot4 = 24 \equiv -1 \pmod 5\)，共 \(\lfloor n/5 \rfloor\) 组完整的，再乘上零头 \((n \bmod 5)!\)；
5 的倍数：\(5, 10, \dots\) 提出 \(5^{\lfloor n/5\rfloor}\) 后剩下 \(\lfloor n/5\rfloor!\)，递归。

\[F(n) = (-1)^{\lfloor n/5\rfloor} \cdot (n \bmod 5)! \cdot F(\lfloor n/5\rfloor) \pmod 5\]

最后把多余的 \(2^z\) 除掉：\(X \equiv F(n) \cdot \mathrm{inv}(2)^z \equiv F(n)\cdot 3^z \pmod 5\)。

import sys


def f_mod5(n):
    """n! 去掉所有因子 5 之后，模 5 的值。循环 log_5(n) ≈ 10 层。"""
    res = 1
    fact = (1, 1, 2, 6, 24)          # 0! .. 4!，下标就是 n mod 5
    # 把递归 F(n) = (-1)^⌊n/5⌋ * (n mod 5)! * F(⌊n/5⌋) 摊平成循环，
    # 每轮把 n 缩成 ⌊n/5⌋，所以只转 log_5(n) 圈
    while n:
        res = res * fact[n % 5] % 5  # 零头 (n mod 5)!
        # 每 5 个连续数里的 4 个非 5 倍数，乘积 1*2*3*4 = 24 ≡ -1 (mod 5)，
        # 共 ⌊n/5⌋ 组，所以整体带一个 (-1)^⌊n/5⌋ 的符号
        if (n // 5) & 1:             # (-1)^⌊n/5⌋：奇数次就取相反数
            res = (5 - res) % 5      # 模 5 下取相反数，写 -res 会得到负下标
        n //= 5                      # 递归到 ⌊n/5⌋!
    return res


def main():
    n = int(sys.stdin.buffer.read().split()[0])
    if n < 2:                        # ★ 0! = 1! = 1 是奇数，公式前提不成立
        sys.stdout.write("1\n")
        return
    z = 0                            # 末尾 0 的个数 = v_5(n!)，勒让德公式
    p = 5
    while p <= n:                    # 逐项累加 ⌊n/5⌋ + ⌊n/25⌋ + ...，只有约 10 层
        z += n // p
        p *= 5
    # f_mod5 已经把因子 5 除干净，但 2 还多除了 z 个，要乘回 2^z 的逆元。
    # 模 5 下 2 的逆元是 3（2*3 = 6 ≡ 1），所以乘 3^z
    r = f_mod5(n) * pow(3, z, 5) % 5             # 3 = inv(2) mod 5
    # n >= 2 时 X 必为偶数，「偶数且模 5 余 r」在 0..9 里唯一确定一个数字
    sys.stdout.write("%d\n" % (0, 6, 2, 8, 4)[r])   # 偶数 + 模 5 余 r -> 唯一末位


main()

复杂度 \(O(\log_5 n) \approx 10\) 层循环。

四个坑：

\(n \le 1\) 必须特判：\(1! = 1\) 是奇数，「\(X\) 是偶数」这个 CRT 前提不成立。从 \(n = 2\) 起公式才对；
\((-1)^k\) 在模 5 下要转正：写 res = (5 - res) % 5，直接写 res = -res 会得到负数，查表时索引越界；
\(z\) 必须用勒让德公式逐项累加，不能写 \(\lfloor n/4 \rfloor\) （那是等比和 \(\frac{n/5}{1-1/5}\) 的近似值，\(n=25\) 时给 6 恰好对，\(n=100\) 时给 25 而真值是 24）；
pow(3, z, 5) 用内置三参数 pow，别手写快速幂（81 章）。

为什么不用 \(O(n)\) 的「逐个乘、随时去 2 去 5」？ \(n = 10^7\) 就是 \(10^7\) 次 Python 层乘法取模，约 5–8 秒，时限 2 秒。 这就是「算法正确但语言不允许」的典型——必须找到 \(O(\log n)\) 的路。

BISHI60 大水题（简单）¶

反复把各位数字相加，直到结果是个位数，输出它。\(1 \le n \le 10^9\)。题面见 BISHI60 原题（牛客）。题解见 solutions/BISHI60.py（已通过官方样例验证）。

这就是数根，一行公式解决：

import sys

n = int(sys.stdin.buffer.read().split()[0])
# 求数位和不改变模 9 的值，反复求到只剩一位就落在 1..9 里。
# 直接写 n % 9 会把 9 的倍数算成 0，先减 1 再加回来正好把 0 平移成 9
sys.stdout.write(str(1 + (n - 1) % 9) + "\n")     # dr(n) = 1 + (n-1) mod 9

两个坑：

n % 9 是错的：\(n = 9\) 时答案是 9 而不是 0。偏移写法才对；
题目保证 \(n \ge 1\)，所以不用处理 \(\mathrm{dr}(0)=0\)。若不保证，加一个 if n == 0 分支。

当然模拟数位求和也只有两三轮（\(10^9\) → 最多 81 → 最多 17 → 个位），完全能过。但公式版说清了「为什么是 9」：\(10 \equiv 1 \pmod 9\)，所以求数位和这个操作不改变模 9 的值。理解了这一条， BISHI13 那种变体才做得动。

BISHI13 九倍平方数（简单，本章视角）¶

可以把某个数位 \(x\) 替换成 \(x^2\)（仅当 \(x^2 < 10\)），问能否让整个数被 9 整除。 \(t \le 10^4\) 组，\(\sum|n| \le 10^5\)。题面见 BISHI13 原题（牛客）。题解见 solutions/BISHI13.py（已通过官方样例验证）。

两步转化，全靠「模 9 = 数位和模 9」这一条。

第一步：\(x^2 < 10\) 只对 \(x \in \{0,1,2,3\}\) 成立，而

\(x\)	\(x^2\)	数位和的增量
0	0	\(+0\)（等于没换）
1	1	\(+0\)（等于没换）
2	4	\(\mathbf{+2}\)
3	9	\(\mathbf{+6}\)

所以真正有用的操作只有两种：把某个 2 变成 4（和 \(+2\)），把某个 3 变成 9（和 \(+6\)）。

第二步：设原数位和为 \(S\)，有 \(c_2\) 个 2、\(c_3\) 个 3，问是否存在 \(0 \le i \le c_2,\ 0 \le j \le c_3\) 使 \((S + 2i + 6j) \equiv 0 \pmod 9\)。因为 \(2i \bmod 9\) 关于 \(i\) 的周期是 9、\(6j \bmod 9\) 的周期是 3， \(i, j\) 各枚举 \(0..8\) 就够，每组最多 81 次判断，与串长无关。

import sys

data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for k in range(1, t + 1):
    s = data[k]                           # 保持 bytes，绝不转 int（O(d²) 且有位数上限）
    total = sum(s) - 48 * len(s)          # ★ bytes 求和再减 '0' 的偏移 = 数位和
    # 只有 2->4（和 +2）和 3->9（和 +6）两种替换真正改变数位和。
    # 2i mod 9 关于 i 的周期是 9，所以做 9 次以上等同于做 i mod 9 次，
    # 上限截到 8 就够，于是每组的枚举量与串长无关
    c2 = min(s.count(50), 8)              # b'2' 的个数，超过 8 个也没用（周期 9）
    c3 = min(s.count(51), 8)              # b'3'
    # 9 | n 等价于 9 整除数位和；枚举替换次数看能否凑出 9 的倍数
    ok = any((total + 2 * i + 6 * j) % 9 == 0
             for i in range(c2 + 1) for j in range(c3 + 1))
    out.append("YES" if ok else "NO")
sys.stdout.write("\n".join(out) + "\n")

两个坑：

绝不把整个数字串转成 int。\(\sum|n| \le 10^5\)，int(s) 是 \(O(d^2)\) 且在 Python 3.11+ 超过 4300 位直接报错。数位和模 9 就够了（85.4 的警告框）；
4、5、6…… 的平方都 \(\ge 10\)，不能替换；1 和 0 替换了等于没换。把这四种情况列成表格再动手，比在脑子里推安全得多。

这题的主讲章节是 49-模拟（读题与状态枚举），本章只承担「模 9 判据 + 周期截断」这一层。

BISHI61 小q的数列（简单）¶

\(f(0)=0\)，\(f(1)=1\)，\(x \ge 2\) 时 \(f(x)=f(\lfloor x/2\rfloor)+f(x \bmod 2)\)。 \(T \le 5\times10^5\) 组询问，每组给 \(n \le 10^{18}\)，输出 \(f(n)\) 以及 该值第一次出现在数列的哪一项。题面见 BISHI61 原题（牛客）。题解见 solutions/BISHI61.py（已通过官方样例验证）。

这是「85.6 四步流水线」的完美演示：打表看前几项 \(0,1,1,2,1,2,2,3,\dots\)，和 \(n\) 的二进制对照一眼就认出来了——

\(f(n) = n\) 的二进制里 1 的个数（popcount）。

归纳证明：\(f(0)=0\)、\(f(1)=1\) 成立；\(x \ge 2\) 时 \(x \bmod 2\) 就是最低位， \(\lfloor x/2 \rfloor\) 是去掉最低位后的数，于是 \(f(x) = \mathrm{popcount}(x \gg 1) + (\text{最低位}) = \mathrm{popcount}(x)\) ✓

第二问：值 \(k\) 第一次出现在哪一项？就是「popcount 等于 \(k\) 的最小非负整数」—— 显然把 \(k\) 个 1 全塞到最低位最小，即 \(2^k-1\)（\(k=0\) 时给 0，公式同样对）。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    # 值 k 第一次出现的下标就是「popcount 恰为 k 的最小非负整数」= 2^k - 1
    # （k 个 1 全塞在最低位最小）。n <= 1e18 < 2^60，64 项足够覆盖
    first = [str((1 << k) - 1) for k in range(64)]   # popcount = k 的最小下标
    out = []
    ap = out.append
    for tok in data[1:t + 1]:
        # f(x) = f(x//2) + f(x%2) 逐层剥掉最低位，累加的正是二进制里 1 的个数
        c = bin(int(tok)).count("1")                 # ★ 3.9 没有 int.bit_count()
        ap(str(c) + " " + first[c])                  # 查表，省掉 5e5 次移位与 str()
    sys.stdout.write("\n".join(out) + "\n")


main()

复杂度：每组 \(O(\log n)\)（bin() 的构造开销），总量 \(5\times10^5 \times 60\) 位但全在 C 层。真去按递推打表是不可能的（\(n\) 到 \(10^{18}\)）。

四个坑：

输入范围写的是 \(n \ge 1\)，但官方样例里出现了 \(n = 0\)（答案 0 0）。代码必须能处理——样例和约束冲突时以样例为准，这是笔试的通用原则；
int.bit_count() 是 3.10+ 的，判题机版本不保证，用 bin(x).count("1")；逐位 while 移位在 \(T=5\times10^5\) 下会慢好几倍；
\(T\) 高达 \(5\times10^5\)，必须 sys.stdin.buffer.read() 整块读 + "\n".join 一次输出，逐行 input()/print() 会被 IO 拖死；
答案的第二部分只有 64 种取值，预先打成字符串表，循环里只做一次列表下标访问，省掉 \(5\times10^5\) 次 (1 << k) - 1 和 str()。

\(n \le 10^{18}\) 超过 int64，C++ 要用 unsigned long long 并小心中间溢出， Python 原生大整数完全无忧——这是本章开头说的「Python 的独特优势」。

BISHI72 中位数之和（较难）¶

长度 \(n\) 的 0/1 数组，\(k\) 为奇数。对所有长度恰为 \(k\) 的子序列 （不必连续，按下标区分），求它们中位数之和，模 \(P = 10^9+7\)。 \(t \le 10^4\) 组，\(\sum n \le 2\times10^5\)。题面见 BISHI72 原题（牛客）。题解见 solutions/BISHI72.py（已通过官方样例验证）。

枚举「子序列本身」是 \(\binom{n}{k}\) 级别的天文数字，只能计数。 85.5 的性质二给出全部思路：

\[\text{中位数为 1} \iff \text{子序列里 1 的个数} \ge h = \frac{k+1}{2}\]

而中位数只能是 0 或 1，所以「中位数之和」= 「中位数为 1 的子序列个数」：

\[\text{答案} = \sum_{j=h}^{\min(k,\,c_1)} \binom{c_1}{j}\binom{c_0}{k-j}\]

（从 \(c_1\) 个 1 里挑 \(j\) 个、从 \(c_0\) 个 0 里挑 \(k-j\) 个。）

验算样例：\(n=5,k=1\)，全是 1 ⟹ \(c_1=5,c_0=0,h=1\)，\(j=1\)： \(\binom51\binom00 = 5\) ✓

import sys

P = 1000000007


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    idx = 1
    cases = []
    mx = 1
    for _ in range(t):                        # ---- 先读完所有数据 ----
        n = int(data[idx]); k = int(data[idx + 1]); idx += 2
        c1 = 0
        for j in range(idx, idx + n):
            if data[j] == b"1":               # 只需要统计 1 的个数
                c1 += 1
        idx += n                              # 游标跳过这一组的 n 个元素
        cases.append((n, k, c1))              # 原数组不必留下，只留下 (n, k, c1)
        if n > mx:
            mx = n                            # 记录全局最大的 n，用来定阶乘表长

    fact = [1] * (mx + 1)                     # ★ 全局只建一次表，表长取最大的 n
    for i in range(2, mx + 1):
        fact[i] = fact[i - 1] * i % P
    inv_fact = [1] * (mx + 1)
    inv_fact[mx] = pow(fact[mx], P - 2, P)    # 只做 1 次快速幂
    for i in range(mx, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % P

    def C(a, b):
        # b > a 时不拦住的话 a - b 变负，inv_fact[a-b] 会取到表尾算出错误答案
        if b < 0 or b > a:                    # 越界一律返回 0，省掉边界判断
            return 0
        return fact[a] * inv_fact[b] % P * inv_fact[a - b] % P

    out = []
    for n, k, c1 in cases:
        c0 = n - c1                           # 0 的个数
        h = (k + 1) // 2                      # 至少要有 h 个 1，中位数才是 1
        s = 0
        # 枚举子序列里 1 的个数 j：从 c1 个 1 里选 j 个、从 c0 个 0 里选 k-j 个。
        # 下界 j >= k - c0 不必显式写，C(c0, k-j) 在 k-j > c0 时自动返回 0
        for j in range(h, min(k, c1) + 1):
            s += C(c1, j) * C(c0, k - j) % P  # 累加时不取模，最后统一模一次
        out.append(str(s % P))
    sys.stdout.write("\n".join(out) + "\n")


main()

复杂度 \(O(\text{maxn} + \sum n)\)：建表一次，每组循环 \(O(k) \le O(n)\)。

四个坑：

阶乘表必须在最外层建一次。逐组重建会退化成 \(O(t \cdot n)\)， \(t = 10^4\) 时直接爆掉。表长取所有测试用例里最大的 \(n\)—— 所以要先把全部输入读完再建表（和 BISHI63 同一个套路）；
求和的上下界：上界 \(\min(k, c_1)\)；下界还要满足 \(k-j \le c_0\) 即 \(j \ge k-c_0\)。 统一用 C(x, y) = 0 (y > x 或 y < 0) 兜住最省心，不必在循环边界里写一堆 max/min；
中位数是排序后第 \(\frac{k+1}{2}\) 个（1-indexed），\(h = (k+1)//2\)。写成 k // 2 会差一位；
按下标计数：同值元素在不同下标算作不同子序列，这正是题意，所以用 \(\binom{c_1}{j}\) 而不是「本质不同的方案」。

这题为什么是「较难」：难点不在组合数（模板在 84.4），而在看出「0/1 值域让求和退化成计数」。一旦想不到这一层，就会去研究「第 \(h\) 小的元素的期望」之类的死路。 值域极小是一个强信号，永远先问自己「能不能按取值分类计数」。

85.8　本章速查¶

公式表¶

名目	公式
等差和	\(S_n = \dfrac{n(a_1+a_n)}{2}\)
等比和	\(S_n = a_1\dfrac{q^n-1}{q-1}\)（\(q=1\) 时 \(=na_1\)，必须特判）
自然数和 / 平方和 / 立方和	\(\dfrac{n(n+1)}{2}\)，\(\dfrac{n(n+1)(2n+1)}{6}\)，\(\left(\dfrac{n(n+1)}{2}\right)^2\)
斐波那契前缀和	\(\sum_{i=1}^{n}F_i = F_{n+2}-1\)
斐波那契倍增	\(F_{2k}=F_k(2F_{k+1}-F_k)\)，\(F_{2k+1}=F_k^2+F_{k+1}^2\)
斐波那契 gcd	\(\gcd(F_m,F_n)=F_{\gcd(m,n)}\)
\(F_n\) 的位数	约 \(0.209n\) 位
勒让德公式	\(v_p(n!)=\sum_{i\ge1}\lfloor n/p^i\rfloor\)
\(n!\) 末尾 0 的个数	\(v_5(n!)\)
数根	\(\mathrm{dr}(n)=1+(n-1)\bmod 9\)（\(n \ge 1\)）
绝对值和最小点	中位数；平方和最小点是平均数

Python 取舍¶

要点	结论
模意义下的递推	每一步都取模，不要算完再取（\(O(k)\) vs \(O(k^2/64)\)）
不取模的代价	\(F_{10^6}\) 有 20.9 万位：0.06 s → 6.4 s
整除	永远 `//`，绝不用 `/`（\(n \ge 2^{53}\) 时 `float` 就错）
模意义下除以 2	先在整数里约掉，或乘 \(\mathrm{inv}2=\frac{p+1}{2}\)
等比和取模	\(q\equiv1\) 时公式分母为 0 → 用分治 `geo_sum`
求 \(F_k\)，\(k \le 10^7\)	线性递推
求 \(F_k\)，\(k \le 10^{18}\)	快速倍增 `fib_pair`（比矩阵快，递归只 60 层）
Binet 通项公式	❌ 浮点，\(n \ge 71\) 就错
递归 + `lru_cache` 求 \(F_k\)	❌ 递归深度 \(= k\)，\(k \ge 1000\) 就爆
`math.factorial`	只在 \(n \le 10^5\) 且要精确值时用；\(10^6\) 要 6 s
多组询问 \(n!\bmod p\)	预处理阶乘表，\(O(n+T)\)
阶乘逆元表	从 `inv[n]` 倒推，只做 1 次快速幂
超长数字串	绝不 `int(s)`（\(O(d^2)\)，3.11+ 还有 4300 位上限）
数位和（`bytes`）	*`sum(s) - 48len(s)`**，比 `sum(map(int,s))` 快 10 倍
popcount	`bin(x).count("1")`；`int.bit_count()` 是 3.10+
求静态中位数	`sorted(a)[n//2]`，快速选择在 Python 里反而更慢
求动态中位数	对顶堆（35 章）
大整数不溢出	Python 的优势（\(10^{18}\) 无忧），也是陷阱（不报错，只变慢）

递推题的流水线¶

步骤	做法
① 打表	小规模暴力算前 10–15 项
② 差分	\(k\) 阶差分为常数 ⟹ \(k\) 次多项式；比值近似常数 ⟹ 指数型
③ 猜通项	等差/等比/不动点/特征方程，按 85.6 的表套
④ 归纳	不能省：前 15 项吻合不代表对
规模判断	\(n\le10^7\) 直接递推；\(n\) 极大 + 线性齐次 → 矩阵快速幂；模意义下找循环节

看到什么 → 想到什么¶

看到什么	想到什么
「\(F_k \bmod p\)，\(k \le 10^6\)」	线性递推 + 每步取模（BISHI62）
「每步走 1 或 2 阶」	斐波那契错位一项（BISHI131）
「\(k \ge 10^9\) 的线性递推」	快速倍增 / 矩阵快速幂
「\(T\) 组询问同一类量」	预处理表（BISHI63）
「\(n!\) 末尾若干位 / 末尾 0」	勒让德公式 + CRT 拆模（BISHI59）
「反复求数位和」	数根 \(1+(n-1)\bmod9\)（BISHI60）
「能否被 9 / 3 整除」	数位和模 9（BISHI13）
「递推里有 \(\lfloor x/2\rfloor\) 和 \(x \bmod 2\)」	二进制数位、popcount（BISHI61）
「\(\sum\\|a_i-x\\|\) 最小」	中位数；带权版累加到总权一半
「变成严格递增的最小代价」	先 \(a_i - i\)，再取中位数
「0/1 数组的某种和」	求和退化成计数（BISHI72）
「值域只有几种取值」	按取值分类计数，\(\sum v\cdot\text{cnt}(v)\)
「超长数字串」	在 `bytes` 上做，别转 `int`

第 85 章 基础数学与递推¶

85.1 等差数列与等比数列¶

公式¶

Python 的三个坑¶

85.2 斐波那契数列¶

下标约定：读题第一件事¶

性质表¶

三种求法与选型¶

Python 的核心取舍：为什么必须随时取模¶

85.3 阶乘¶

增长速度与 math.factorial 的边界¶

阶乘取模：预处理表¶

勒让德公式：\(n!\) 里有多少个质因子 \(p\)¶

85.4 数位处理¶

三种拆位方式¶

数位和与整除判定¶

数根（digital root）¶

「数位」不只是十进制¶

数位构造类问题¶

85.5 中位数的性质¶

定义¶

性质一：绝对值和的最小点¶

经典模型¶

性质二：0/1 数组的中位数只能是 0 或 1¶

求中位数的四种方式¶

85.6 递推式的求解思路¶

四步流水线¶

① 打表：先有数据再有结论¶

② 差分验证：判断是不是多项式¶

③ 猜通项：按递推形式套模板¶

④ 数学归纳：让猜测变成证明¶

什么时候完全不需要通项¶

85.7 例题¶

BISHI62 斐波那契数列（简单）¶

BISHI131 数楼梯（简单）¶

BISHI63 计算阶乘（简单）¶

BISHI59 阶乘末尾非零数字（中等）¶

BISHI60 大水题（简单）¶

BISHI13 九倍平方数（简单，本章视角）¶

BISHI61 小q的数列（简单）¶

BISHI72 中位数之和（较难）¶

85.8 本章速查¶

公式表¶

Python 取舍¶

递推题的流水线¶

看到什么 → 想到什么¶

第 85 章　基础数学与递推¶

85.1　等差数列与等比数列¶

85.2　斐波那契数列¶

85.3　阶乘¶

增长速度与 `math.factorial` 的边界¶

85.4　数位处理¶

85.5　中位数的性质¶

85.6　递推式的求解思路¶

85.7　例题¶

85.8　本章速查¶