日食

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

状态二元组只有 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

形式化题目

给定质数 P≤10007P \le 10007 和常数 A,B,X,Y,Z,CA,B,X,Y,Z,C(均满足 0≤A,B,X,Y,Z,C<P0 \le A,B,X,Y,Z,C < P),定义序列

S1=A,S2=B,Si=(XSi−1+YSi−2+Z) mod P(i≥3) S_1 = A,\qquad S_2 = B,\qquad S_i = (X S_{i-1} + Y S_{i-2} + Z) \bmod P \quad (i \ge 3)

有 Q≤2×104Q \le 2\times 10^4 次询问,每次给出 1≤L≤R≤10181 \le L \le R \le 10^{18},求

#{ i∈[L,R]:Si=C } \#\{\, i \in [L,R] : S_i = C \,\}

多组数据,T≤2T \le 2。

天数上限 101810^{18} 说明它只可能出现在「算完整周期个数」这一步,而不是逐天枚举:逐天递推是 O(R)O(R),必然超时。

正解

思路

关键观察:序列的“状态”只有 P2P^2 种。 第 ii 项完全由 (Si−2,Si−1)(S_{i-2}, S_{i-1}) 这对数决定,而每一维都只有 PP 种取值,所以二元组 (Si−1,Si)(S_{i-1}, S_i) 最多 P2≈108P^2 \approx 10^8 种。从 (A,B)(A,B) 出发,最多走 P2+1P^2+1 步就必然撞到已经出现过的二元组,然后开始循环。PP 只有一万,P2P^2 是可以承受的规模——这就是为什么模数被刻意设得这么小。

于是把序列拆成「进圈前的一段尾巴 + 一个循环节」,预处理出尾巴长度和圈长之后,[L,R][L,R] 的答案就是两个前缀计数之差。

为什么还要分 YY 是否为 00? 因为尾巴是否存在取决于转移是否可逆。考虑把状态 (u,v)(u,v) 映到 (v,(Xv+Yu+Z) mod P)(v, (Xv+Yu+Z) \bmod P):

  • 若 Y≢0(modP)Y \not\equiv 0 \pmod P,由 PP 是质数知 YY 有乘法逆元。若两个状态映到同一结果 (v,w)(v,w),那么两状态的第二维都等于 vv,再比第一维:Yu+Xv+Z≡Yu′+Xv+ZY u + Xv + Z \equiv Y u' + Xv + Z,两边约掉后 u≡u′u \equiv u'。所以转移是整个状态空间上的单射,而状态数有限,它就是双射(置换)。置换的每个点都在一个纯环上,因此序列是纯周期的:第一次重复出现的状态必定就是初始状态 (A,B)(A,B),尾巴长度为 00,周期 K≤P2K \le P^2。
  • 若 Y=0Y = 0,递归退化成一阶 Si=(XSi−1+Z) mod PS_i = (X S_{i-1}+Z) \bmod P,起作用的状态只是单个数值 Si−1S_{i-1},状态数掉到 PP。一阶映射不一定可逆(例如 X=0X=0 时所有值都映到 ZZ),于是可能先走一段尾巴再进圈。注意第 11 项 AA 根本不参与后面的递推,它一定属于尾巴;真正会进圈的只有第 22 项以后的部分。此时尾巴长度 <P< P、圈长 ≤P\le P。

预处理:把一圈上的命中位置记下来。 记 f(n)f(n) 为前 nn 天里 Si=CS_i=C 的天数。设尾巴长 offset、圈长 KK、一圈内命中 cntPeriod 天,则

f(n)={命中表上二分,n≤offset+KtailCnt+⌊n−offsetK⌋⋅cntPeriod+(圈上第 1∼(n−offset) mod K 位的命中数),n>offset+K f(n)=\begin{cases} \text{命中表上二分}, & n \le \text{offset}+K \\[4pt] \text{tailCnt} + \left\lfloor \dfrac{n-\text{offset}}{K} \right\rfloor \cdot \text{cntPeriod} + \bigl(\text{圈上第 } 1 \sim (n-\text{offset})\bmod K \text{ 位的命中数}\bigr), & n > \text{offset}+K \end{cases}

其中 tailCnt(尾巴里的命中数)和「圈上前若干位命中数」都只是同一个升序命中位置表上的二分。于是每组询问 [L,R][L,R] 只需算 f(R)−f(L−1)f(R)-f(L-1),O(log⁡)O(\log)。

实现上的几个坑:

  1. AA 或 BB 本身就可能等于 CC,第 1,21,2 项要先行登记。
  2. 纯周期情形下,递推的停止条件是 (Si−1,Si)=(A,B)(S_{i-1},S_i) = (A,B) 重新出现,此时 K=i−2K = i-2。这个循环判定与数据无关,Y≠0Y\ne 0 时最坏要跑 P2≈108P^2 \approx 10^8 次递推;T≤2T\le 2 也只有 2×1082\times10^8 次,20002000 ms 足够。
  3. 停止时第 K+1K+1 项的值与第 11 项相同,如果 S1=CS_1 = C,位置 K+1K+1 会被顺手登记进命中表,属于重复计数,必须剔除(只保留位置 ≤K\le K 的);K=1K=1 时第 22 项同理。
  4. L−1L-1 可能为 00,f(0)=0f(0)=0。
  5. cntPeriod 与 ⌊(R−offset)/K⌋\lfloor (R-\text{offset})/K \rfloor 相乘可能很大(K=1K=1、R=1018R=10^{18}),必须用 64 位整数。
  6. 不要为了查前缀和去开一个长度 P2P^2 的 int 数组(400400 MB),把命中位置存成有序表 + 二分更省;C++ 版只在「纯周期」分支用 P2P^2 位(12.512.5 MB)的位图标记一圈上的命中位置。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 题目:日食(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;
}

复杂度

  • 时间:预处理在 Y≠0Y \ne 0 时是 O(P2)O(P^2)(枚举一整圈,最坏 P2≈108P^2 \approx 10^8 次递推), Y=0Y = 0 时只需 O(P)O(P) 步;T≤2T \le 2,最坏约 2×1082\times 10^8 次递推, C++ 实测最慢一组 1.141.14 s(限时 2000 ms)。每组询问 O(log⁡)O(\log)(命中表上二分), 总计 O(Qlog⁡Q)O(Q\log Q)。
  • 空间:C++ 用 P2P^2 位(12.512.5 MB)的位图标记一圈上的命中位置,另有 O(Q)O(Q) 的询问数组; Python 只存命中位置列表(一圈内命中数通常约 K/PK/P 量级),O(P+∣hits∣+Q)O(P + |\text{hits}| + Q)。
  • 数据类型:R≤1018R \le 10^{18},周期个数与圈内计数相乘可达 101810^{18} 量级, 必须全程 64 位整数(long long;Python 大整数天然无此问题)。

总结

本题的题眼是「模数很小 ⇒ 状态空间有限 ⇒ 序列必然循环」。判出循环之后,R≤1018R \le 10^{18} 的区间计数就退化成周期除法加前缀查表。

容易被忽略的是 Y=0Y=0 的退化情形:此时转移不再可逆,序列会先走一段尾巴,直接套用「从第 11 项开始纯周期」会算错;而 Y≠0Y \ne 0 时因为 PP 是质数、YY 可逆,才敢断定第一次重复的状态就是初始状态。这类「用模数的代数性质判断转移是否可逆」的推理,是周期类题目里最常见的分水岭。