序列

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

通过 Golomb 自描述序列的特性对元素出现次数分块,预处理块的右端点和前缀贡献,使用二分查找加速求解连续分布的位置和。

OJ: roj

题目 ID: 5016

难度:提高+/省选-

标签:模拟二分前缀和

创建: 2026-10-08 20:22

更新: 2026-10-08 20:22

形式化题目

已知一个序列从 1,2,21, 2, 2 开始。后续构造规则为:当我们看到第 ii 个数是 viv_i 时,就在序列末尾追加 viv_i 个 ii。 (例如:第 33 个数是 22,所以我们在序列后面写 22 个 33,变成 1,2,2,3,31, 2, 2, 3, 3。第 44 个数是 33,就写 33 个 44。) 最后,这个序列变成了 1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,…1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, \dots 这也是著名的 Golomb 序列。

题面定义了两个关键量:

  • last(N)last(N):数字 NN 最后一次出现在序列中的位置。
  • 输出:TT 行,每行一个整数,代表 last(last(N)) mod (109+7)last(last(N)) \bmod (10^9+7) 的值。

给定 N≤109N \le 10^9,T≤2×103T \le 2 \times 10^3,多组测试用例。

正解

思路

因为序列的每一项代表某个数字出现的次数,所以 A[]A[] 本身就是自己的「块长度表」:即值 vv 在序列中恰好出现 A[v]A[v] 次。 此时 last(N)last(N) 代表数字 NN 最后出现的位置,这个位置就等于序列中小于等于 NN 的所有项的总数。如果我们记 A[i]A[i] 是值 ii 出现的次数,且设前缀和 S[k]=∑i=1kA[i]S[k] = \sum_{i=1}^k A[i],那么显然:

last(N)=S[N]last(N) = S[N]

对于题目的终极目标 last(last(N))last(last(N)),直接代入可得:

last(last(N))=S[S[N]]last(last(N)) = S[S[N]]

如何高效计算 S[S[N]]S[S[N]]? 由于 S[N]S[N] 代表了「前 NN 个数字在序列里的总个数」,而前 NN 个数字中,每个数字 v≤Nv \le N 都恰好各自出现了 A[v]A[v] 次,并占据了原序列中的对应位置。那么其所代表的最终总位置,也就是:

S[S[N]]=∑v≤Nv⋅A[v]S[S[N]] = \sum_{v \le N} v \cdot A[v]

注意,这并不等于 ∑i≤Nlast(i)\sum_{i \le N} last(i)。比如当 N=10N=10 时,∑i≤10last(i)=146\sum_{i \le 10} last(i) = 146,而正确答案是 ∑v≤10v⋅A[v]=217\sum_{v \le 10} v \cdot A[v] = 217。

当 S[K]≥109S[K] \ge 10^9 时,KK 大约是 438744438744 量级。因此我们不可能、也没有必要开出 10910^9 大小的数组。我们可以利用按值分块的思路:

  • 第 kk 块对应于数字 kk,这一块有 A[k]A[k] 个元素。
  • 第 kk 块覆盖的原序列位置区间为 (S[k−1],S[k]](S[k-1], S[k]]。
  • 它对结果 S[S[N]]S[S[N]] 的贡献就是块里的所有位置编号乘以 kk。

具体算法:

  1. 预处理:按自描述特性利用双指针(或者利用前缀递推递推公式 A[n+1]=1+A[n+1−A[A[n]]]A[n+1] = 1 + A[n+1-A[A[n]]])找出前 KK 个块的右端点(满足 S[K]≥109S[K] \ge 10^9)。
  2. 同时对前 kk 块完整贡献进行等差数列求和。因为 S[S[N]]S[S[N]] 可以达到 ∼5×1017\sim 5 \times 10^{17} 级别,所有过程求和均使用 long long 或至少 64 位整数运算避免溢出(如果是其他语言可以用 __int128 或自带的大整数,最后一步再进行取模)。
  3. 查询:对于每一个询问 NN,在 SS 数组上用 bisect 二分定位到相应的块,累加该块之前的完整前缀和,以及该块内只到 NN 的残缺等差部分的贡献。

代码

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 20:14
# update_at: 2026-10-08 20:14

import sys
from bisect import bisect_left

MOD = 10 ** 9 + 7
INV2 = 500000004  # 2 在模 1e9+7 下的逆元,给等差数列求和公式用
LIMIT = 10 ** 9   # 题面 N 的上限;last(K) 首次 >= 1e9 时 K ≈ 4.4e5


def build_ends(limit: int) -> list[int]:
    """构造块右端点 ends:ends[v] = last(v) = 序列中 <= v 的项数;同时返回出现次数 a。

    序列自描述:值 v 的出现次数 a[v] 就是 Golomb 序列第 v 项,满足
    a[1]=1, a[2]=2, a[n+1] = 1 + a[n+1-a[a[n]]]。
    """
    a = [0, 1, 2]
    ends = [0, 1, 3]
    while ends[-1] < limit:
        a.append(1 + a[len(a) - a[a[-1]]])
        ends.append(ends[-1] + a[-1])
    return ends


def build_pref(ends: list[int]) -> list[int]:
    """pref[k] = 前 k 块对答案的完整贡献(第 i 块 = 块号 i × 块内位置编号之和)。"""
    pref = [0] * len(ends)
    for k in range(1, len(ends)):
        left, right = ends[k - 1] + 1, ends[k]
        # 位置编号之和用等差数列:块 k 覆盖 (ends[k-1], ends[k]],值恒为 k
        pref[k] = (pref[k - 1] + k * (left + right) * (right - left + 1) * INV2) % MOD
    return pref


def last_last(n: int, ends: list[int], pref: list[int]) -> int:
    """求 last(last(n)) mod MOD:定位 n 所在块 g,整块查前缀和 + 末块等差部分。"""
    g = bisect_left(ends, n)  # 最小的 g 使 ends[g] >= n,即 n 所在块号
    left = ends[g - 1] + 1
    return (pref[g - 1] + g * (left + n) * (n - left + 1) * INV2) % MOD


def solve() -> None:
    ends = build_ends(LIMIT)
    pref = build_pref(ends)
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    print("\n".join(str(last_last(next(data), ends, pref)) for _ in range(T)))


if __name__ == "__main__":
    solve()
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 20:12
 * update_at: 2026-10-08 20:12
 */
// 一本通 1680《序列》/ roj 5016:分块 + 前缀和 + 二分
//
// 题面:序列从 1,2,2 开始;读到第 i 个数 v_i 就往后写 v_i 个 i(题面例子:
//   第 3 个数是 2 ⇒ 写 2 个 3;第 4 个数是 3 ⇒ 写 3 个 4),得到
//   1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,...。这就是 Golomb 自描述序列。
//   last(x) = x 最后一次出现的位置 = a[1]+...+a[x](a[v] 为 v 出现的次数)。
//   求 last(last(N)) mod (1e9+7)。
//
// 关键恒等式:last(last(N)) = Σ_{v=1..N} v * a[v]。
//   于是把出现的值相同的项看作一块:第 k 块(值恒为 k)覆盖位置区间
//   (last(k-1), last(k)],共 a[k] 个位置。答案就是
//   Σ_{k} k * (第 k 块覆盖的位置编号之和) —— 即「位置 × 该位置上的值」的总和。
//
// 复杂度:N <= 1e9 时块号只到 438744,预处理 O(K)(K≈4.4e5);
//   单次询问在 last(k) 数组上二分定位块号,O(log K)。

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

typedef long long ll;

const ll MOD = 1000000007LL;
const ll INV2 = 500000004LL;   // 2 在模 1e9+7 下的逆元
const ll LIMIT = 1000000000LL; // 题面 N 的上限
const int MAXK = 500005;       // K ≈ 4.4e5(last(K) 首次 >= 1e9),留足余量

struct Block {
    ll appear_cnt; // a[k]:数字 k 在序列中出现的次数,也是第 k 块的元素个数
    ll end_pos;    // last(k) = a[1]+...+a[k],第 k 块的右端点
};

Block block[MAXK]; // block[0].end_pos = 0;第 k 块覆盖 (end_pos[k-1], end_pos[k]]
ll pref[MAXK];     // pref[k] = 前 k 块对答案的完整贡献之和 (mod MOD)
int block_cnt;     // 已构造的块数,也是覆盖 N <= 1e9 所需的块号上限

// 按 Golomb 序列的自描述规则构造块表:
// 值 p 总共要出现 a[p] 次,所以连续产生 a[p] 个「值为 p」的块。
void build_block() {
    block[0].appear_cnt = 0;
    block[0].end_pos = 0;
    block[1].appear_cnt = 1;
    block[1].end_pos = 1;
    block[2].appear_cnt = 2;
    block[2].end_pos = 3;
    block[3].appear_cnt = 2; // 题面给出的初始段 1,2,2 决定 a[3] = 2
    block[3].end_pos = 5;

    int k = 3;      // 当前块号
    int value = 3;  // 正在复制的块号:值 value 要出现 block[value].appear_cnt 次
    ll used = 0;    // 值 value 已经复制出去的次数
    while (block[k].end_pos < LIMIT) {
        if (used == block[value].appear_cnt) { // 值 value 已经用完,换下一个值
            value++;
            used = 0;
        }
        k++;
        block[k].appear_cnt = value;
        block[k].end_pos = block[k - 1].end_pos + value;
        used++;
    }
    block_cnt = k;

    // pref[k] = Σ_{i<=k} i * (第 i 块的位置编号之和),位置编号之和用等差数列公式
    pref[0] = 0;
    for (int i = 1; i <= block_cnt; i++) {
        ll left_end = block[i - 1].end_pos + 1;
        ll right_end = block[i].end_pos;
        ll cnt = right_end - left_end + 1;
        ll pos_sum = (left_end + right_end) % MOD * (cnt % MOD) % MOD * INV2 % MOD;
        pref[i] = (pref[i - 1] + i % MOD * pos_sum) % MOD;
    }
}

// 求 last(last(n)) mod MOD = Σ_{v<=n} v*a[v]:定位 n 所在块,整块查前缀和,
// 最后一块只取到 n 为止的等差部分。
ll query(ll n) {
    int lo = 1;
    int hi = block_cnt;
    while (lo < hi) { // 找最小的 g 使 end_pos[g] >= n
        int mid = (lo + hi) / 2;
        if (block[mid].end_pos >= n) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    ll g = lo;
    ll left_end = block[g - 1].end_pos + 1;
    ll cnt = n - left_end + 1;
    ll pos_sum = (left_end + n) % MOD * (cnt % MOD) % MOD * INV2 % MOD;
    return (pref[g - 1] + g % MOD * pos_sum) % MOD;
}

void solve() {
    ll T;
    if (!(cin >> T)) {
        return;
    }
    for (ll i = 1; i <= T; i++) {
        ll n;
        cin >> n;
        cout << query(n) << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    build_block();
    solve();

    return 0;
}

复杂度

  • 时间复杂度:预处理阶段需扩展序列到 K≈4.4×105K \approx 4.4 \times 10^5,时间为 O(K)O(K)。查询时对于 TT 组用例,每个用例二分查找的时间为 O(log⁡K)O(\log K),总时间为 O(K+Tlog⁡K)O(K + T \log K)。
  • 空间复杂度:由于要记录前 KK 个数字的块右端点位置和前缀和,需要用到 O(K)O(K) 大小的数组或列表,这在 10910^9 限制下完美符合空间条件。

总结

  • 题意核心为“看到第 ii 个数是 viv_i,就在末尾追加 viv_i 个 ii”,这构成了非常经典的自描述结构(Golomb 序列)。
  • last(N) 是值 NN 最后一次出现的位置,本题就是求解 last(last(N)) mod (109+7)last(last(N)) \bmod (10^9+7)。
  • 核心恒等式推导: 由于值 ≤N\le N 的项数恰为 S[N]S[N],因此 last(N)=S[N]last(N) = S[N]。进而有 last(last(N))=S[S[N]]last(last(N)) = S[S[N]]。等价的另一形式为 S[S[N]]=∑v≤Nv⋅A[v]S[S[N]] = \sum_{v \le N} v \cdot A[v],因为 S[N]S[N] 位置之前的项正好由各个 v≤Nv \le N 各贡献 A[v]A[v] 个构成。
  • 必须澄清的陷阱:这不等于 ∑i≤Nlast(i)\sum_{i \le N} last(i),这是最初推导极容易混淆的地方。
  • 因为 NN 最大为 10910^9,不能直接记录整个数列;而是通过按值分块的方式只需记录 ≈4.4×105\approx 4.4 \times 10^5 规模的端点,接着配合二分查找在 O(log⁡K)O(\log K) 找到目标块。
  • 计算时用到的 S[S[N]]S[S[N]] 的中间量可以高达 5×10175 \times 10^{17},为了防止精度丢失,只在加上各块部分后才取模运算,并且乘法求和过程中需使用至少 64 位宽的大整数类型保证中间溢出安全。