状态二元组只有 P² 种且 P≤10007,Y≠0 时转移可逆、序列从第 1 项起纯周期(K≤P²),Y=0 时退化为一阶带尾巴;预先扫出一圈的命中位置,再用「尾巴 + 完整周期 + 残缺周期」的前缀计数 O(1) 回答每次 [L,R]。
OJ: roj
题目 ID: 1809
难度:提高
标签:数学周期前缀和python
创建: 2026-10-07 11:20
更新: 2026-10-07 11:20
形式化题目
给定质数
有
多组数据,
天数上限
正解
思路
关键观察:序列的“状态”只有
于是把序列拆成「进圈前的一段尾巴 + 一个循环节」,预处理出尾巴长度和圈长之后,
为什么还要分
- 若
,由 是质数知 有乘法逆元。若两个状态映到同一结果 ,那么两状态的第二维都等于 ,再比第一维: ,两边约掉后 。所以转移是整个状态空间上的单射,而状态数有限,它就是双射(置换)。置换的每个点都在一个纯环上,因此序列是纯周期的:第一次重复出现的状态必定就是初始状态 ,尾巴长度为 ,周期 。 - 若
,递归退化成一阶 ,起作用的状态只是单个数值 ,状态数掉到 。一阶映射不一定可逆(例如 时所有值都映到 ),于是可能先走一段尾巴再进圈。注意第 项 根本不参与后面的递推,它一定属于尾巴;真正会进圈的只有第 项以后的部分。此时尾巴长度 、圈长 。
预处理:把一圈上的命中位置记下来。 记 offset、圈长 cntPeriod 天,则
其中 tailCnt(尾巴里的命中数)和「圈上前若干位命中数」都只是同一个升序命中位置表上的二分。于是每组询问
实现上的几个坑:
或 本身就可能等于 ,第 项要先行登记。 - 纯周期情形下,递推的停止条件是
重新出现,此时 。这个循环判定与数据无关, 时最坏要跑 次递推; 也只有 次, ms 足够。 - 停止时第
项的值与第 项相同,如果 ,位置 会被顺手登记进命中表,属于重复计数,必须剔除(只保留位置 的); 时第 项同理。 可能为 , 。 cntPeriod与相乘可能很大( 、 ),必须用 64 位整数。 - 不要为了查前缀和去开一个长度
的 int数组(MB),把命中位置存成有序表 + 二分更省;C++ 版只在「纯周期」分支用 位( MB)的位图标记一圈上的命中位置。
代码
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-07 11:20
# update_at: 2026-10-07 11:20
import sys
from bisect import bisect_right
# 命中位置表:一圈内满足 S_i == C 的位置(升序,位置从 1 开始)
type Hits = list[int]
# 序列结构:(圈外尾巴长度 offset, 周期 K, 表格 hits 覆盖第 1..offset+K 天)
type Cycle = tuple[int, int, Hits]
def walk_second_order(a: int, b: int, x: int, y: int, z: int, p: int, c: int) -> Cycle:
"""Y!=0 时状态转移可逆,序列从第 1 项起就是纯周期:返回 (offset=0, 周期 K, 一圈内的命中位置)。"""
hits: Hits = [i for i, v in enumerate((a, b), 1) if v == c]
prev, cur, i = a, b, 3
while True:
nxt = (x * cur + y * prev + z) % p
if nxt == b and cur == a: # 状态 (S(i-1), S(i)) 回到 (A, B),恰好走满一圈
k = i - 2
break
if nxt == c:
hits.append(i)
prev, cur, i = cur, nxt, i + 1
# 循环点在第 K+1 项与第 1 项同值,重复登记要去掉;K=1 时第 2 项同理
return 0, k, [i for i in hits if i <= k]
def walk_first_order(a: int, b: int, x: int, z: int, p: int, c: int) -> Cycle:
"""Y=0 退化成一阶递推,状态只由单项决定:返回 (进圈前的位置数 offset, 周期 K, 命中位置)。"""
hits: Hits = [1] if a == c else [] # 第 1 项不影响后续,永远属于圈外尾巴,单独登记
first = [-1] * p # 每个取值首次出现的位置
cur, i = b, 2
while first[cur] < 0: # 第一次撞上旧值,说明从这里开始进圈
first[cur] = i
if cur == c:
hits.append(i)
cur = (x * cur + z) % p
i += 1
return first[cur] - 1, i - first[cur], hits
def count_up_to(days: int, offset: int, k: int, hits: Hits) -> int:
"""前 days 天(days >= 0)中 S_i == C 的天数 = 尾巴 + 完整周期 + 残缺周期。"""
if days <= offset + k: # 还没走完「尾巴 + 第一圈」,直接查表
return bisect_right(hits, days)
tail = bisect_right(hits, offset) # 尾巴里的命中数
cycles, left = divmod(days - offset, k)
return tail + cycles * (len(hits) - tail) + bisect_right(hits, offset + left) - tail
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
t = next(data)
for _ in range(t):
a, b, x, y, z, p, c, q = (next(data) for _ in range(8))
queries = [(next(data), next(data)) for _ in range(q)] # Q 组 L R
offset, k, hits = (walk_second_order(a, b, x, y, z, p, c) if y
else walk_first_order(a, b, x, z, p, c))
out += [str(count_up_to(r, offset, k, hits) - count_up_to(l - 1, offset, k, hits))
for l, r in queries]
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 题目:日食(ROJ 1809)
* 来源:信息学奥赛一本通 · 高手训练篇
*
* 题意:S1=A, S2=B, Si=(X*S(i-1)+Y*S(i-2)+Z) mod P (i>=3),P 为质数且 P<=10007。
* Q 次询问 [L,R],问 L..R 中有多少天满足 Si=C。
*
* 核心:模数 P 很小,状态二元组 (S(i-1),S(i)) 只有 P^2 种,序列必然循环。
* - Y != 0 时转移可逆(Y 在模 P 下有逆元),是双射,序列为"纯周期":
* 周期 K <= P^2,从第 1 项就开始循环,前缀尾巴长度 offset = 0。
* - Y == 0 时递推退化成一阶,状态只有单项,先走一段长度 <= P 的尾巴再进圈。
* 对每组数据把一整圈枚举出来(记为"圈上第 r 位是否等于 C"),
* 于是前 N 天中满足 Si=C 的天数 = (N-offset)/K * 圈内个数 + 圈上前 (N-offset)%K 位个数,
* 询问即可 O(1)(实现上用一次离线扫描求所有需要的圈上前缀数)。
*
* 复杂度:时间 O(T*(P^2 + Q log Q)),空间 O(P^2/64 + Q)。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXP = 10007; /* P 的上限 */
const int MAXBITS = MAXP * MAXP + 128; /* 周期上限 P^2,再留冗余 */
static unsigned long long bits[(MAXBITS >> 6) + 2]; /* 圈上标记位图,约 12.5 MB */
inline void bitSet(int i) { bits[i >> 6] |= 1ULL << (i & 63); }
/* ---------------- 快速读入 ---------------- */
static char ibuf[1 << 16];
static int ilen = 0, ipos = 0;
inline int gc() {
if (ipos == ilen) {
ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);
ipos = 0;
if (ilen <= 0) return -1;
}
return ibuf[ipos++];
}
inline ll readInt() {
int c = gc();
while (c != -1 && (c < '0' || c > '9') && c != '-') c = gc();
bool neg = false;
if (c == '-') { neg = true; c = gc(); }
ll x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return neg ? -x : x;
}
int main() {
int T = (int)readInt();
string out;
out.reserve(1 << 16);
char tmp[24];
for (int tc = 0; tc < T; tc++) {
ll A = readInt(), B = readInt(), X = readInt(), Y = readInt();
ll Z = readInt(), P = readInt(), C = readInt(), Q = readInt();
vector<ll> ql(Q), qr(Q);
for (int j = 0; j < Q; j++) { ql[j] = readInt(); qr[j] = readInt(); }
if (Y == 0) {
/* ---------- 一阶退化:S_i = (X*S_{i-1} + Z) mod P ---------- */
vector<int> firstOcc((size_t)P, -1); /* 每个取值首次出现的位置 */
vector<int> seq; /* 第 1..offset+K 项 */
seq.reserve((size_t)P + 2);
seq.push_back((int)A); /* 第 1 项 */
ll i = 2, offset = 0, K = 1;
int cur = (int)B;
while (true) {
if (firstOcc[cur] != -1) {
offset = firstOcc[cur] - 1; /* 尾巴长度(含第 1 项) */
K = i - firstOcc[cur]; /* 圈长 */
break;
}
firstOcc[cur] = (int)i;
seq.push_back(cur);
cur = (int)(((ll)X * cur + Z) % P);
i++;
}
/* 前缀和:pref[t] = 前 t 项中等于 C 的个数 */
int tot = (int)(offset + K);
vector<int> pref((size_t)tot + 1, 0);
for (int t = 1; t <= tot; t++) pref[t] = pref[t - 1] + (seq[t - 1] == C ? 1 : 0);
ll cntPeriod = pref[tot] - pref[(size_t)offset];
auto countUpTo = [&](ll N) -> ll {
if (N <= 0) return 0;
if (N <= (ll)tot) return pref[(size_t)N];
ll rem = N - offset;
ll cycles = rem / K, left = rem % K;
return (ll)pref[(size_t)offset] + cycles * cntPeriod
+ (pref[(size_t)(offset + left)] - pref[(size_t)offset]);
};
for (int j = 0; j < Q; j++) {
ll ans = countUpTo(qr[j]) - countUpTo(ql[j] - 1);
int len = snprintf(tmp, sizeof(tmp), "%lld\n", ans);
out.append(tmp, len);
}
} else {
/* ---------- 二阶可逆:纯周期,从第 1 项起循环 ---------- */
int prev = (int)A, cur = (int)B;
if (A == C) bitSet(0); /* 第 1 项 */
if (B == C) bitSet(1); /* 第 2 项 */
ll K = 1, i = 3;
while (true) {
int nxt = (int)(((ll)X * cur + (ll)Y * prev + Z) % P);
if (cur == (int)A && nxt == (int)B) { K = i - 2; break; }
if (nxt == C) bitSet((int)(i - 1));
prev = cur; cur = nxt;
i++;
}
/* 统计圈上前 K 位(位下标 0..K-1)里等于 C 的个数 */
ll cnt = 0, fullWords = K >> 6;
for (ll w = 0; w < fullWords; w++) cnt += __builtin_popcountll(bits[w]);
int restBits = (int)(K & 63);
if (restBits) cnt += __builtin_popcountll(bits[fullWords] & ((1ULL << restBits) - 1));
/* 离线:收集所有需要的圈上前缀长度 m = N%K */
vector<ll> need;
need.reserve(2 * (size_t)Q);
for (int j = 0; j < Q; j++) {
need.push_back(qr[j] % K);
need.push_back((ql[j] - 1) % K);
}
sort(need.begin(), need.end());
need.erase(unique(need.begin(), need.end()), need.end());
/* 升序扫描位图,得到每个 m 对应的"圈上前 m 位中等于 C 的个数" */
vector<ll> tblVals(need.size());
ll w = 0, acc = 0;
for (size_t t = 0; t < need.size(); t++) {
ll target = need[t];
while ((w + 1) * 64 <= target) { acc += __builtin_popcountll(bits[w]); w++; }
ll part = acc, rem = target - w * 64;
if (rem > 0) part += __builtin_popcountll(bits[w] & ((1ULL << rem) - 1));
tblVals[t] = part;
}
/* 查询圈上前 m 位的个数:在 need 里定位 m 的下标 */
auto queryCyc = [&](ll m) -> ll {
size_t pos = (size_t)(lower_bound(need.begin(), need.end(), m) - need.begin());
return tblVals[pos];
};
for (int j = 0; j < Q; j++) {
ll cntR = (qr[j] / K) * cnt + queryCyc(qr[j] % K);
ll cntL = ((ql[j] - 1) / K) * cnt + queryCyc((ql[j] - 1) % K);
ll ans = cntR - cntL;
int len = snprintf(tmp, sizeof(tmp), "%lld\n", ans);
out.append(tmp, len);
}
/* 清空本次用到的位图,供下一组数据使用 */
ll used = (K >> 6) + 1;
for (ll w2 = 0; w2 < used; w2++) bits[w2] = 0;
}
}
fwrite(out.data(), 1, out.size(), stdout);
return 0;
}复杂度
- 时间:预处理在
时是 (枚举一整圈,最坏 次递推), 时只需 步; ,最坏约 次递推, C++ 实测最慢一组 s(限时 2000 ms)。每组询问 (命中表上二分), 总计 。 - 空间:C++ 用
位( MB)的位图标记一圈上的命中位置,另有 的询问数组; Python 只存命中位置列表(一圈内命中数通常约 量级), 。 - 数据类型:
,周期个数与圈内计数相乘可达 量级, 必须全程 64 位整数( long long;Python 大整数天然无此问题)。
总结
本题的题眼是「模数很小 ⇒ 状态空间有限 ⇒ 序列必然循环」。判出循环之后,
容易被忽略的是