题目链接

数列

题目描述

一个特殊的数列 定义如下：

  • (当 )

给出任意一个正整数 ()，求该数列的第 项对 32767 取模的结果。

输入包含多组测试数据。

解题思路

这是一个标准的线性递推关系问题。由于 的最大值达到了 ，并且有多组测试数据，我们需要一个高效的计算方法。

方法：动态规划 (DP) / 预计算

  1. 识别问题： 这是一个二阶线性递推数列，类似于斐波那契数列。第 项的值完全由前两项决定。

  2. 选择策略：

    • 如果只有一次查询且 非常大（例如 ），我们会使用矩阵快速幂，其时间复杂度为 。
    • 但在本题中， 的上限是 ，并且有多组查询。直接的迭代计算是可行的（），但每次查询都重新计算会很浪费。
    • 因此，最佳策略是一次性预计算出所有可能被查询到的项（从第 1 项到第 1,000,000 项），并将它们存储在一个数组中。之后，每次查询都只需要 的时间进行查表。

  3. 算法流程：

    • 创建一个大小为 的数组（或向量），我们称之为 dp。
    • 设置初始值：dp[1] = 1, dp[2] = 2。
    • 递推计算：使用一个循环，从 i = 3 到 1,000,000，根据递推公式 dp[i] = 2 * dp[i-1] + dp[i-2] 来计算每一项。
    • 取模操作：为了防止数字溢出并满足题目要求，在每一步计算中都要对结果进行取模操作：dp[i] = (2 * dp[i-1] + dp[i-2]) % 32767。
    • 处理查询：预计算完成后，对于每一组测试数据给出的 ，直接输出 dp[k] 的值即可。

代码

#include <iostream>
#include <vector>

using namespace std;

const int MAX_K = 1000000;
const int MOD = 32767;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 预计算
    vector<int> dp(MAX_K + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= MAX_K; ++i) {
        dp[i] = (2 * dp[i - 1] + dp[i - 2]) % MOD;
    }

    int n;
    cin >> n;
    while (n--) {
        int k;
        cin >> k;
        cout << dp[k] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MAX_K = 1000000;
    private static final int MOD = 32767;

    public static void main(String[] args) {
        // 预计算
        int[] dp = new int[MAX_K + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= MAX_K; i++) {
            dp[i] = (2 * dp[i - 1] + dp[i - 2]) % MOD;
        }

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int k = sc.nextInt();
            System.out.println(dp[k]);
        }
    }
}

import sys

MAX_K = 1000000
MOD = 32767

# 预计算
dp = [0] * (MAX_K + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, MAX_K + 1):
    dp[i] = (2 * dp[i-1] + dp[i-2]) % MOD

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        for _ in range(n):
            k_str = sys.stdin.readline()
            if not k_str: break
            k = int(k_str)
            print(dp[k])
            
    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：动态规划 (DP) / 预计算

  • 时间复杂度：，其中 是 的最大值（）， 是测试数据的组数。主要开销在于一次性的预计算，之后的每次查询都是 。

  • 空间复杂度：。需要一个大小与 的最大值相当的数组来存储所有预计算的结果。