M02786: Pell数列

dfs, dp, http://cs101.openjudge.cn/practice/02786/

Pell数列a1, a2, a3, ...的定义是这样的，a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k，要求Pell数列的第k项模上32767是多少。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

输出

n行，每行输出对应一个输入。输出应是一个非负整数。

样例输入

2
1
8

样例输出

1
408

应用题面给出的递推公式。

dp = [0]*(1000000+1)
dp[1], dp[2] = 1, 2
for i in range(3, 1000000+1):
    dp[i] = (2*dp[i-1] + dp[i-2])%32767

for _ in range(int(input())):
    k = int(input())
    print(dp[k])

#2300011786 裘思远
from functools import lru_cache

@lru_cache(maxsize=None)
def series(n):
    if n>2:
        a,b=1,2
        for i in range(n-2):
            a,b=b%32767,(a+2*b)%32767
        return b
    elif n==2:
        return 2
    else:
        return 1

n=int(input())
for _ in range(n):
    k=int(input())
    ans=series(k)
    print(ans)

经过计算和观察，能够发现 Pell 数列在模 32767 下的值会在某个点开始周期性地重复，具体的周期长度在很多情况下是 150。这意味着只需计算前 150 项的值，然后可以用这些值来回答任何 k 的查询，只需将 k 对 150 取模即可得到结果。

#2300011786 裘思远
from functools import lru_cache

@lru_cache(maxsize=None)
def series(n):
    if n>2:
        return (series(n-1)*2+series(n-2))%32767
    elif n==2:
        return 2
    else:
        return 1

n=int(input())
for _ in range(n):
    k=int(input())%150
    ans=series(k)
    print(ans)

这是典型的 矩阵 + 快速幂 求 Pell 数列取模问题。 直接写出符合题意、可通过在线评测的 高效 Python 实现（O(log k) 每次计算）。

---

✅ 思路简要

给定递推： $a_1=1,a_2=2,a_n=2a_{n-1}+a_{n-2}$

矩阵形式：

$$\left[\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{a}_{n-1}\\ a_{n-2}\end{array}\right]$$

因此：

$$\left[\begin{array}{c}{a}_k\\ a_{k-1}\end{array}\right]={\left[\begin{array}{cc}2& 1\\ 1& 0\end{array}\right]}^{k-2}\left[\begin{array}{c}{a}_2\\ a_1\end{array}\right]$$

模数为 32767。

---

Python 实现

MOD = 32767

def matmul(A, B):
    # 2x2 矩阵乘法取模
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD]
    ]

def mat_pow(M, n):
    # 快速幂计算 M^n
    res = [[1, 0], [0, 1]]  # 单位矩阵
    while n:
        if n & 1:
            res = matmul(res, M)
        M = matmul(M, M)
        n //= 2
    return res

def pell(k):
    if k == 1:
        return 1
    if k == 2:
        return 2
    M = [[2, 1],
         [1, 0]]
    Mn = mat_pow(M, k - 2)
    # [a_k, a_{k-1}] = Mn * [a_2, a_1]
    return (Mn[0][0] * 2 + Mn[0][1] * 1) % MOD

# 读取输入
n = int(input())
for _ in range(n):
    k = int(input())
    print(pell(k))

说明

• 时间复杂度：O(log k)

• 空间复杂度：O(1)

• 通过矩阵快速幂，无需递归或线性 DP，就能高效计算到 (k < 10^6) 的项。