形式化题目（按题面）

题目来源为 [NOIP2006-普及] 数列。给定数列 $a_n$，已知 $a_1, a_2$ 两项，满足递推式

求 $\displaystyle\sum_{i=1}^{n} a_i^2 \bmod (10^9+7)$。

输入格式：第一行整数 $T$，随后 $T$ 行每行 $5$ 个整数 n a1 a2 x y。 输出格式：$T$ 行，每行一个整数。 数据范围：$T = 30000$，$1 \le n \le 10^{18}$，$1 \le a_1, a_2, x, y \le 10^9$。

这是一道标准的矩阵快速幂题：把状态构造成 $(a_n^2,\ a_n a_{n-1},\ a_{n-1}^2,\ S_n)$，用 $4 \times 4$ 矩阵幂求 $n$ 项平方和。

数据实况（与题面完全错位）

实际文件形态

1
2
3
4seqgame0.in = b'20\r\n4 6 12 14 10 20 11 9 16 5 13 2 7 18 19 1 3 17 8 15'
seqgame0.out = b'3'
seqgame3.in = b'1\r\n999'                      seqgame3.out = b'0'
seqgame2.in = b'1000\r\n1 2 4 2 4 5 4 5 7 ...'  seqgame2.out = b'335'

即：第一行一个整数 $N$，第二行 $N$ 个整数。 每个 .out 只有一个很小的整数（$0 \sim 335$）。

判据一：按题面格式无法解析

题面要求读入 $T$ 组、每组 5 个数（n a1 a2 x y）， 而 seqgame0.in 只有 2 行：20 与 20 个数。 seqgame3.in 只有 1 和 999 —— 根本无法构成一组 n a1 a2 x y （缺少 4 个数）⇒ 题面输入格式在数据上不成立。

判据二：输出格式完全不匹配

题面输出是 $T$ 行整数（样例 40 / 4193 / 480929868，可达 $10^9$ 量级）， 而所有 .out 都只有 1 个 $\le 335$ 的小整数 ⇒ 题面输出格式在数据上不成立。

判据三（★ 最强）：seqgame2 是人工生成的，与递推无关

seqgame2 的值集合恰为 $\{v : 1 \le v \le 502,\ v \bmod 3 \ne 0\}$， 共 335 个不同值；且答案为 335。 其差分序列严格周期为 1, 2, -2, 2, 1, -1 ⇒ 这是按规则生成的构造数据（“值域中排除 3 的倍数”）， 与 Fibonacci 型递推数列毫无关系。

判据四：三个点是 $1..N$ 的排列

即输入是「数组」而不是「递推参数」，这进一步锁死题面无效。

判据五：候选清单与匹配数表（穷尽努力）

对每个候选统计量，算出 10 个点的值并与 .out 逐点比对 （out = [3, 42, 335, 0, 9, 10, 8, 6, 23, 30]）：

最佳候选仅 4/10（LIS(a_i % 4 == 2)、LIS(a_i % 2 == 0)）， 没有任何候选达到 10/10。

已系统排除的候选族（成批试验）

1. 子序列族：LIS / LNDS / LDS / 最长双调 / 最长交替 / 最长回文 / 最长等差 / 最长等比 / 最长 $|a_{i+1}-a_i| = d$（$d = 1..20$）/ 最长 $a_{i+1} - a_i = d$ / $a_{i+1} \ge a_i + c$（$c = 1..30$）—— 以及对差集 $\{1\},\{2\},\ldots,\{1..k\}$（$k \le 8$）、 随机二元/三元差子集（$\{1..8\}$ 的全部 2、3 元组合）的受限 LIS。
2. 子数组族：最长上升 / 下降 / 相邻差 1 / 相邻差 $\pm 1$ / 值互异 / 值连续 / max−min ≤ $W$ / 和 ≤ 阈值。
3. 计数族：逆序对、相邻上升/下降/相等数、记录数、波峰波谷数、 $a_i = 2a_j$ 对数、局部极值数。
4. 值链族：$dp[v] = dp[v-d]+1$（$d = 1..20$）、乘链 $v \to 2v$ / $3v$、 整除链、gcd 链。
5. 图 / 递推族：函数图 i -> a[i] 最长路径、循环节长度、连通分量数；跳跃游戏 （i -> i+a_i 的最少步数、可达性）；$i \to i \cdot a_i$。
6. 变换 × 统计（约 $17$ 变换 $\times 15$ 统计 $= 255$ 组）：逆序排列、 取负、$a_i \pm c i$（$c = -4..4$）、$\bmod k$、$\lfloor a_i/k \rfloor$（$k \in \{2..16\}$）、 xor i、and i、前缀和、累积极值、秩变换、差分、符号序列。
7. 仿射关系 DP（$\alpha(y-x) + \beta(j-i) + \gamma x + \delta \gtrless 0$， 约 17000 组系数）：无一命中。
8. RSK 形状 / Greene 不变量：形状首行 $=$ LIS、行数 $=$ LDS、 Durfee 方块、共轭形状 —— 均不等于输出。

单点偶合（★ 明确标注：非 10/10）

• seqgame2：n_distinct = 335 恰等于答案 335；
• seqgame0：函数图 i -> i + a[i] 的最少跳跃步数 = 3 恰等于答案 3；
• seqgame0：最长相邻差 1 子序列 = 3 也恰好命中。

这三条都只在单点成立，在其余 9 点上立即失败 （如 jump_steps 在其余点是 $2,2,2,2,1,2,2$，而答案是 $42,335,\ldots$） ⇒ 判定为巧合，不足以反解。

结论

题面与数据错位，在当前信息下无法反解真实考点。

• 题面（递推数列平方和 + 矩阵快速幂）的输入格式在数据上不成立 （第 2 行的 $N$ 个数无法解释成一组 n a1 a2 x y）；
• 题面的输出格式也不成立（应有 $T$ 行大整数，实为 1 个 $\le 335$ 的小整数）；
• 数据本身有明确的构造痕迹（seqgame2 排除 3 的倍数、三个点是 $1..N$ 排列）， 说明它确实属于另一道题，但该题的题面未随数据一同保存；
• 在约 60+ 类候选统计量、255 组变换×统计、17000 组仿射关系 的系统穷举下，没有任何候选达到 10/10，最佳仅 4/10 ⇒ 不足以断定真实考点。

无 std.cpp、无 data.py、无生成脚本，缺少反解的最后一环。

处理方式（2026-10-10 更新：补齐按题面的代码实现）

代码按【题面】实现（矩阵快速幂求递推数列平方和），不按数据 —— 因为数据属于另一道题（见上文五条判据），照数据写等于编造规律（T31）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#include <cstdio>

typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1000000007LL;
const int SZ = 4;

ll a1, a2, x, y;

// 状态向量 v = (a_n^2, a_n * a_{n-1}, a_{n-1}^2, S_n)，S_n = sum_{i=1}^{n} a_i^2
//   a_{n+1}^2   = x^2 * a_n^2 + 2xy * a_n a_{n-1} + y^2 * a_{n-1}^2
//   a_{n+1}a_n  = x   * a_n^2 + y   * a_n a_{n-1}
//   a_n^2       = a_n^2
//   S_{n+1}     = S_n + a_{n+1}^2
struct Mat {
    ll v[SZ][SZ];
};

Mat mul(const Mat &p, const Mat &q) {
    Mat r;
    for (int i = 0; i < SZ; i++)
        for (int j = 0; j < SZ; j++) {
            ull acc = 0; // 用 128 位安全的累加方式：每步取模
            for (int k = 0; k < SZ; k++)
                acc = (acc + (ull)(p.v[i][k] * q.v[k][j] % MOD)) % MOD;
            r.v[i][j] = (ll)acc;
        }
    return r;
}

Mat pow(Mat m, ll e) {
    Mat r;
    for (int i = 0; i < SZ; i++)
        for (int j = 0; j < SZ; j++)
            r.v[i][j] = (i == j);
    while (e > 0) {
        if (e & 1) r = mul(r, m);
        m = mul(m, m);
        e >>= 1;
    }
    return r;
}

ll sq(ll v) { return v % MOD * (v % MOD) % MOD; }

// 返回 sum_{i=1}^{n} a_i^2 mod MOD
ll solve_one(ll n) {
    if (n <= 0) return 0;
    if (n == 1) return sq(a1);
    if (n == 2) return (sq(a1) + sq(a2)) % MOD;
    // v_2 = (a2^2, a2 a1, a1^2, S_2)
    Mat T;
    ll xx = x % MOD, yy = y % MOD;
    T.v[0][0] = xx * xx % MOD; T.v[0][1] = 2 * xx % MOD * yy % MOD; T.v[0][2] = yy * yy % MOD; T.v[0][3] = 0;
    T.v[1][0] = xx;            T.v[1][1] = yy;                      T.v[1][2] = 0;            T.v[1][3] = 0;
    T.v[2][0] = 1;             T.v[2][1] = 0;                       T.v[2][2] = 0;            T.v[2][3] = 0;
    T.v[3][0] = T.v[0][0];     T.v[3][1] = T.v[0][1];               T.v[3][2] = T.v[0][2];    T.v[3][3] = 1;
    // ★ S_{n+1} = S_n + a_{n+1}^2，而 a_{n+1}^2 = T 第 0 行的线性组合
    //   ⇒ S 行 = (x², 2xy, y², 1)，不是 (0,0,0,1) —— 写成后者是本文件曾出过的 bug
    Mat P = pow(T, n - 2);
    ll a2m = a2 % MOD, a1m = a1 % MOD;
    ll v0 = a2m * a2m % MOD;
    ll v1 = a2m * a1m % MOD;
    ll v2 = a1m * a1m % MOD;
    ll v3 = (v0 + v2) % MOD; // S_2
    ll r0 = (ll)((ull)P.v[3][0] * v0 % MOD + (ull)P.v[3][1] * v1 % MOD + (ull)P.v[3][2] * v2 % MOD + (ull)P.v[3][3] * v3 % MOD) % MOD;
    return r0;
}

int main() {
    int t;
    if (scanf("%d", &t) != 1) return 0;
    while (t-- > 0) {
        ll n;
        if (scanf("%lld %lld %lld %lld %lld", &n, &a1, &a2, &x, &y) != 5) break;
        printf("%lld\n", solve_one(n));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#!/usr/bin/env python3
# 2026-10-10 11:00

import sys

MOD = 10 ** 9 + 7


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    t = int(next(it))
    out = []
    for _ in range(t):
        n = int(next(it)); a1 = int(next(it)); a2 = int(next(it))
        x = int(next(it)); y = int(next(it))
        out.append(str(square_sum(n, a1, a2, x, y)))
    sys.stdout.write('\n'.join(out) + '\n')


def square_sum(n: int, a1: int, a2: int, x: int, y: int) -> int:
    """sum_{i=1}^{n} a_i^2 mod MOD，其中 a_n = x*a_{n-1} + y*a_{n-2}。"""
    if n <= 0:
        return 0
    if n == 1:
        return a1 * a1 % MOD
    # 迭代：O(n) 对本题 n <= 1e18 不可行，但纯标准库无矩阵乘法库；
    # n 较小时直接迭代，较大时用 4x4 矩阵快速幂（手写）。
    if n <= 64:
        prev2, prev1 = a1 % MOD, a2 % MOD
        s = (prev2 * prev2 + prev1 * prev1) % MOD
        for _ in range(n - 2):
            cur = (x * prev1 + y * prev2) % MOD
            s = (s + cur * cur) % MOD
            prev2, prev1 = prev1, cur
        return s
    return mat_pow_sum(n, a1, a2, x, y)


def mat_pow_sum(n: int, a1: int, a2: int, x: int, y: int) -> int:
    """状态 v = (a_n^2, a_n a_{n-1}, a_{n-1}^2, S_n) 的 4x4 矩阵快速幂。"""

    def mul(p, q):
        r = [[0] * 4 for _ in range(4)]
        for i in range(4):
            pi = p[i]
            for k in range(4):
                pik = pi[k]
                if pik:
                    qk = q[k]
                    for j in range(4):
                        r[i][j] = (r[i][j] + pik * qk[j]) % MOD
        return r

    def pow_mat(m, e):
        r = [[int(i == j) for j in range(4)] for i in range(4)]
        while e > 0:
            if e & 1:
                r = mul(r, m)
            m = mul(m, m)
            e >>= 1
        return r

    T = [
        [x * x % MOD, 2 * x * y % MOD, y * y % MOD, 0],
        [x % MOD, y % MOD, 0, 0],
        [1, 0, 0, 0],
        [x * x % MOD, 2 * x * y % MOD, y * y % MOD, 1],  # ★ S 行 = a² 行 + 1（曾是 (0,0,0,1) 的 bug）
    ]
    P = pow_mat(T, n - 2)
    a1m, a2m = a1 % MOD, a2 % MOD
    v0 = a2m * a2m % MOD
    v1 = a2m * a1m % MOD
    v2 = a1m * a1m % MOD
    v3 = (v0 + v2) % MOD
    row = P[3]
    return (row[0] * v0 + row[1] * v1 + row[2] * v2 + row[3] * v3) % MOD


if __name__ == '__main__':
    solve()

实现验证（与数据无关的独立验证）

★ 证据等级的诚实声明（T14）

1
2
3
4
5
6✅ 代码是【题面算法】的正确实现（矩阵快速幂，O(log n) 每组）
    —— 有 Fibonacci 恒等式 + 双语交叉 + 暴力对拍三重独立验证
✅ 但【本题的真实数据是另一道题的】（见上文判据）
    ⇒ 这份代码在 data/ 的 10 个点上【预期只有 1/10 通过】
      （该点是巧合；其余点输入格式都不成立）
⚠ 本题不得按数据验证；若未来取回 seqgame* 的真实题面，需另写按数据的实现

建议

若后续能取回 seqgame* 对应的原始题面或 std.cpp，本题可再补一篇按数据的题解； 当前状态下代码按题面实现、数据错位如实标注（T65）。