通过 Golomb 自描述序列的特性对元素出现次数分块,预处理块的右端点和前缀贡献,使用二分查找加速求解连续分布的位置和。
OJ: roj
题目 ID: 5016
难度:提高+/省选-
标签:模拟二分前缀和
创建: 2026-10-08 20:22
更新: 2026-10-08 20:22
形式化题目
已知一个序列从
题面定义了两个关键量:
:数字 最后一次出现在序列中的位置。 - 输出:
行,每行一个整数,代表 的值。
给定
正解
思路
因为序列的每一项代表某个数字出现的次数,所以
对于题目的终极目标
如何高效计算
注意,这并不等于
当
- 第
块对应于数字 ,这一块有 个元素。 - 第
块覆盖的原序列位置区间为 。 - 它对结果
的贡献就是块里的所有位置编号乘以 。
具体算法:
- 预处理:按自描述特性利用双指针(或者利用前缀递推递推公式
)找出前 个块的右端点(满足 )。 - 同时对前
块完整贡献进行等差数列求和。因为 可以达到 级别,所有过程求和均使用 long long或至少 64 位整数运算避免溢出(如果是其他语言可以用__int128或自带的大整数,最后一步再进行取模)。 - 查询:对于每一个询问
,在 数组上用 bisect二分定位到相应的块,累加该块之前的完整前缀和,以及该块内只到的残缺等差部分的贡献。
代码
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;
}复杂度
- 时间复杂度:预处理阶段需扩展序列到
,时间为 。查询时对于 组用例,每个用例二分查找的时间为 ,总时间为 。 - 空间复杂度:由于要记录前
个数字的块右端点位置和前缀和,需要用到 大小的数组或列表,这在 限制下完美符合空间条件。
总结
- 题意核心为“看到第
个数是 ,就在末尾追加 个 ”,这构成了非常经典的自描述结构(Golomb 序列)。 last(N)是值最后一次出现的位置,本题就是求解 。 - 核心恒等式推导: 由于值
的项数恰为 ,因此 。进而有 。等价的另一形式为 ,因为 位置之前的项正好由各个 各贡献 个构成。 - 必须澄清的陷阱:这不等于
,这是最初推导极容易混淆的地方。 - 因为
最大为 ,不能直接记录整个数列;而是通过按值分块的方式只需记录 规模的端点,接着配合二分查找在 找到目标块。 - 计算时用到的
的中间量可以高达 ,为了防止精度丢失,只在加上各块部分后才取模运算,并且乘法求和过程中需使用至少 64 位宽的大整数类型保证中间溢出安全。