数列

GitHub跳转原题关系图返回列表

每个 m 元子集恰好给出 2 个合法数列,答案为 2^(n+1)-n^2-n-2;n 有 5000 位,按字符串读入并用费马小定理降幂。

OJ: roj

题目 ID: 1799

难度:提高+/省选-

标签:数学组合计数费马小定理大整数python

创建: 2026-10-08 03:52

更新: 2026-10-08 03:52

形式化题目

从 {1,2,…,n}\{1, 2, \dots, n\} 中取若干个数排成长度 m⩾3m \geqslant 3 的数列 a1,a2,…,ama_1, a_2, \dots, a_m, 对每个 3⩽k⩽m3 \leqslant k \leqslant m 都要求

(ak−ak−2)(ak−1−ak−2)<0,(a_k - a_{k-2})(a_{k-1} - a_{k-2}) < 0,

即 ak−2a_{k-2} 严格位于 ak−1a_{k-1} 与 aka_k 之间。求所有满足条件的数列个数,模 109+710^9+7 输出。 其中 3⩽n⩽1050003 \leqslant n \leqslant 10^{5000}。

正解

思路

先看暴力能给我们什么。 直接按定义搜索:顺序枚举 a1,a2a_1, a_2,之后每一次在 「比 min⁡(ak−2,ak−1)\min(a_{k-2},a_{k-1}) 更小」或「比 max⁡(ak−2,ak−1)\max(a_{k-2},a_{k-1}) 更大」的数里挑没出现过的项, 每走一步只要长度 ⩾3\geqslant 3 就计数一次。这个搜索在 n⩽10n \leqslant 10 时可以秒出结果, 把答案记成 f(n)f(n):

nn 3 4 5 6 7 8 9 10
f(n)f(n) 2 10 32 84 198 438 932 1936

暴力为什么撑不住。 搜索树在第 kk 层要枚举 O(n)O(n) 个候选值,深度又是 O(n)O(n), n⩽10n \leqslant 10 就已经是百万级的枚举;题面的 n⩽2000n \leqslant 2000 那一档配合 dp[i][j][k]dp[i][j][k](位置、上一项、当前项)也只能做到 O(n3)O(n^3), 而 n⩽105000n \leqslant 10^{5000} 意味着 nn 本身连 64 位整数都装不下——必须脱离逐项递推, 去找数列整体结构的不变量。

关键观察:合法数列由元素集合唯一决定(只差一个朝向)。 把条件改写成相邻差的形式。 令 di=ai+1−aid_i = a_{i+1} - a_i,则 (ak−ak−2)(ak−1−ak−2)<0(a_k-a_{k-2})(a_{k-1}-a_{k-2}) < 0 等价于

(dk−1+dk) dk−1<0  ⟺  dk−1, dk 异号且 ∣dk∣>∣dk−1∣.(d_{k-1} + d_k)\, d_{k-1} < 0 \iff d_{k-1},\, d_k \text{ 异号且 } |d_k| > |d_{k-1}|.

也就是说:相邻差必须符号交替,并且绝对值严格递增。由此可以顺着读下去:

  • k=3k = 3:先定朝向。若 a2<a1<a3a_2 < a_1 < a_3,则 d1=a2−a1<0d_1 = a_2 - a_1 < 0、d2=a3−a1>0d_2 = a_3 - a_1 > 0;
  • k=4k = 4:d2>0d_2 > 0,所以必须 d3<0d_3 < 0 且 ∣d3∣>d2|d_3| > d_2,于是 a4<a2a_4 < a_2。 此时四条大小关系被锁死为 a4<a2<a1<a3a_4 < a_2 < a_1 < a_3;
  • k=5k = 5:d3<0d_3 < 0,所以必须 d4>0d_4 > 0 且 d4>∣d3∣=a2−a4d_4 > |d_3| = a_2 - a_4, 由 a4<a2<a1<a3a_4 < a_2 < a_1 < a_3 得 a4+(a2−a4)=a2a_4 + (a_2-a_4) = a_2,故 a5>a2a_5 > a_2; 又 d4>∣d3∣d_4 > |d_3| 结合 a2a_2 的位置可进一步确定 a5>a3a_5 > a_3,链条扩展为 a4<a2<a1<a3<a5a_4 < a_2 < a_1 < a_3 < a_5。

每加一项,大小顺序都是被前两项唯一决定的:峰值只可能往右往高走、谷值只可能往左往低走, 交替进行。于是:

  1. 所有 aia_i 必两两不同;
  2. 一旦 a1,a2,a3a_1, a_2, a_3 的朝向确定(a2<a1<a3a_2 < a_1 < a_3 或 a3<a1<a2a_3 < a_1 < a_2), 后面每一项在完整有序链中的位置就被唯一确定。

于是得到双射。 从 {1,…,n}\{1,\dots,n\} 任选 mm 个互不相同的数,排成 s1<s2<⋯<sms_1 < s_2 < \dots < s_m。 朝向「a2<a1<a3a_2 < a_1 < a_3」时,链上从左到右读作 am,am−1,…,a4,a2,a1,a3,a5,…,am−1a_m, a_{m-1}, \dots, a_4, a_2, a_1, a_3, a_5, \dots, a_{m-1}(奇偶两路各占一侧), 把它对齐到 s1,…,sms_1, \dots, s_m 就还原出唯一的数列;朝向反过来则对称地给出另一个。 所以每个大小为 m⩾3m \geqslant 3 的子集恰好对应 2 个合法数列,长度为 mm 的方案数是 2(nm)2\binom{n}{m}。

闭式。 对所有 m⩾3m \geqslant 3 求和,用二项式定理:

Ans=2∑m=3n(nm)=2(2n−(n0)−(n1)−(n2))=2n+1−n2−n−2.\text{Ans} = 2\sum_{m=3}^{n} \binom{n}{m} = 2\left(2^n - \binom{n}{0} - \binom{n}{1} - \binom{n}{2}\right) = 2^{n+1} - n^2 - n - 2.

用上面的暴力表逐点核对:n=3→2n=3 \to 2、4→104 \to 10、5→325 \to 32、6→846 \to 84、 7→1987 \to 198、8→4388 \to 438、9→9329 \to 932、10→193610 \to 1936,全部吻合;题面样例 n=3→2n=3 \to 2、n=666→805846404n=666 \to 805846404 同样吻合。

剩下的问题只是算这个式子。 nn 有 5000 位十进制,不能读进整型,所以按字符串逐位 用 Horner 法取模,维护两个余数即可:

  • n mod pn \bmod p 用来算多项式部分 n2+n+2n^2 + n + 2;
  • n mod (p−1)n \bmod (p-1) 配合费马小定理给指数降幂:因 p=109+7p = 10^9+7 为素数且 gcd⁡(2,p)=1\gcd(2,p)=1, 有 2p−1≡1(modp)2^{p-1} \equiv 1 \pmod p,故 2 n+1≡2 (n+1) mod (p−1)(modp)2^{\,n+1} \equiv 2^{\,(n+1) \bmod (p-1)} \pmod p。

两个模数不能混用:指数只能对 p−1p-1 取模,底数与多项式只能对 pp 取模。 最后 2n+1−(n2+n+2)2^{n+1} - (n^2+n+2) 可能为负,取模时要补一个 pp。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 03:52
 * update_at: 2026-10-08 03:52
 */
// main.cpp:数列 —— 每个 m 元子集恰好对应 2 个合法数列(首三项的两种朝向),
// 故答案为 2 * sum_{m=3}^{n} C(n,m) = 2^(n+1) - n^2 - n - 2。
// n 最多 5000 位十进制,只能按字符串读入;指数用费马小定理降到模 (p-1)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL; // 取模质数 p
const ll PERIOD = MOD - 1;   // 费马小定理给出的 2 的指数周期 p-1

// 十进制大串按 Horner 法逐位取模,得到 n mod m
ll mod_of_digits(const string &s, ll m) {
    ll r = 0;
    for (char c : s) r = (r * 10 + (c - '0')) % m;
    return r;
}

// 快速幂:base^e mod MOD
ll power(ll base, ll e) {
    ll r = 1;
    base %= MOD;
    while (e > 0) {
        if (e & 1) r = r * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!(cin >> s)) return 0;
    size_t pos = s.find_first_not_of('0'); // 题面保证 n>=3,这里只做健壮性处理
    s = (pos == string::npos) ? string("0") : s.substr(pos);

    ll np = mod_of_digits(s, MOD);     // n mod p,用于多项式部分 n^2+n+2
    ll nm1 = mod_of_digits(s, PERIOD); // n mod (p-1),用于指数部分
    ll exponent = (nm1 + 1) % PERIOD;  // (n+1) mod (p-1)

    ll pow2 = power(2, exponent);              // 2^(n+1) mod p
    ll poly = (np * np % MOD + np + 2) % MOD;  // n^2 + n + 2 mod p
    ll ans = (pow2 - poly + MOD) % MOD;

    cout << ans << '\n';
    return 0;
}

Python 版本同一算法:用 Python 的任意精度整数做外层减法,但降幂的字符串取模仍按位进行, 不依赖 int() 解析超大十进制串(避免 CPython 3.11+ 的 4300 位转换上限)。

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:52
# update_at: 2026-10-08 03:52

import sys

MOD = 10 ** 9 + 7  # 取模质数 p;指数降幂用它的周期 p-1
PERIOD = MOD - 1


def reduce_mod(digits: str, m: int) -> int:
    """把十进制数字串按 Horner 法逐位取模,避开 int() 的 4300 位字符串上限。"""
    r = 0
    for ch in digits:
        r = (r * 10 + (ord(ch) - 48)) % m
    return r


def solve() -> None:
    # 输入只有一行一个大整数:取出该 token,去掉前导零(题面保证 n >= 3)。
    token = next(iter(sys.stdin.buffer.read().split()))
    n_digits = token.decode().lstrip('0') or '0'

    n_mod_p = reduce_mod(n_digits, MOD)        # n mod p,用于 n^2 + n + 2
    n_mod_pm1 = reduce_mod(n_digits, PERIOD)   # n mod (p-1),费马小定理降幂用
    exponent = (n_mod_pm1 + 1) % PERIOD        # (n+1) mod (p-1)

    ans = (pow(2, exponent, MOD) - n_mod_p * n_mod_p - n_mod_p - 2) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

复杂度

  • 时间:字符串逐位取模 O(L)O(L)(L⩽5001L \leqslant 5001 为 nn 的十进制位数), 快速幂 O(log⁡p)O(\log p),合计 O(L+log⁡p)O(L + \log p)。
  • 空间:O(L)O(L) 存输入串(逐位处理则 O(1)O(1))。

总结

这道题的难点完全在发现结构而不是计算:条件看似是局部约束,但写成分差 did_i 之后 就是「符号交替 + 绝对值严格递增」,逼得每一项的大小位置被前两项唯一锁死, 于是合法数列与「子集 + 一个朝向」形成双射,答案坍缩成 2n+1−n2−n−22^{n+1} - n^2 - n - 2。

一旦拿到闭式,剩下的只是工程细节:读 5000 位十进制串取模、用费马小定理给指数降幂、 注意指数模 p−1p-1 与多项式模 pp 不能混。

关于数据的说明:本仓库该题的 data/ 由素材源自带的 data.py 生成, 题面来自网络重建(素材源里注明检索题解未果,std.cpp 为自研), 因此出题意图与官方原题可能存在偏差;但闭式已用 n⩽10n \leqslant 10 的暴力枚举独立验证, 与素材源 std.cpp(等价地写成 2n+1−4n−(n−1)(n−2)2^{n+1} - 4n - (n-1)(n-2))以及全部 10 个随仓数据点一致。