Pell数列

题目描述

Pell 数列： $a_1 = 1$ ， $a_2 = 2$ ， $a_k = 2a_{k-1} + a_{k-2}$ （ $k > 2$ ）。

输入 $n$ 组正整数 $k$ （ $1 \le k < 10^6$ ），输出 $a_k \bmod 32767$ 。

样例输入 2 1 8，样例输出 1 408。

思路

先读入所有询问求出最大下标 $k_{\max}$ ，一次线性递推预计算到 $k_{\max}$ 并把每步对 $32767$ 取模的结果存入数组，之后每个询问直接查表输出。

参考代码

Python 版：

python

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#!/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-09-29 22:55
# update_at: 2026-09-29 22:55

import sys

MOD = 32767  # 题目要求的模数


def pell_table(limit: int) -> list[int]:
    """pell[k] = Pell 数列第 k 项对 32767 取模，下标从 1 开始，只算到 limit。"""
    pell = [0, 1, 2]  # a(1) = 1，a(2) = 2，下标 0 只做占位
    for k in range(3, limit + 1):
        pell.append((2 * pell[k - 1] + pell[k - 2]) % MOD)  # 每步取模，表内恒为 32767 以内
    return pell


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)  # 测试组数
    queries = [next(data) for _ in range(T)]  # 先收齐全部询问，才知道要预计算到哪个位置

    pell = pell_table(max(queries))  # 一次线性递推，所有询问共享同一张表
    print('\n'.join(map(str, (pell[k] for k in queries))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * 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-05 04:48
 * update_at: 2026-10-05 04:48
 */
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

const int MOD = 32767;      // 题目要求的模数
const int MAXK = 1000000;   // k 的上界（严格小于 1e6，取 1e6 足够）

int pell[MAXK + 1];         // pell[k] 表示第 k 项对 MOD 取模的结果
int query[MAXK];            // 所有询问，最多 MAXK 个

// 预计算 Pell 数列到 limit，pell[k] 直接保存取模后的答案
void build_pell(int limit) {
    pell[1] = 1;
    pell[2] = 2;
    for (int i = 3; i <= limit; i++) {
        pell[i] = (2 * pell[i - 1] + pell[i - 2]) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    int max_k = 0;
    for (int i = 0; i < n; i++) {
        cin >> query[i];
        if (query[i] > max_k) max_k = query[i];
    }

    build_pell(max_k);

    for (int i = 0; i < n; i++) {
        cout << pell[query[i]] << '\n';
    }

    return 0;
}

目录

题目描述

思路

参考代码