解题思路

这是一道数列模运算题目，主要思路如下：

  1. 数列特点分析：

    • 需要求解第 项模 的结果

  2. 关键发现：

    • 由于是模 的结果
    • 数列会出现循环
    • 经过计算，循环周期为

  3. 解决方案：

    • 预处理前150项
    • 对输入的 取模
    • 直接输出对应位置的值

代码

#include <iostream>
using namespace std;

const int MOD = 32767;
const int PERIOD = 150;

int main() {
    // 预处理数列
    int result[PERIOD] = {0, 1, 2};
    for(int i = 3; i < PERIOD; ++i) {
        result[i] = (2 * result[i-1] + result[i-2]) % MOD;
    }
    
    // 处理查询
    int t;
    cin >> t;
    while(t--) {
        int k;
        cin >> k;
        cout << result[k % PERIOD] << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 32767;
    static final int PERIOD = 150;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 预处理数列
        int[] result = new int[PERIOD];
        result[1] = 1;
        result[2] = 2;
        for(int i = 3; i < PERIOD; ++i) {
            result[i] = (2 * result[i-1] + result[i-2]) % MOD;
        }
        
        // 处理查询
        int t = sc.nextInt();
        while(t-- > 0) {
            int k = sc.nextInt();
            System.out.println(result[k % PERIOD]);
        }
    }
}

MOD = 32767
PERIOD = 150

def main():
    # 预处理数列
    result = [0] * PERIOD
    result[1] = 1
    result[2] = 2
    for i in range(3, PERIOD):
        result[i] = (2 * result[i-1] + result[i-2]) % MOD
    
    # 处理查询
    t = int(input())
    for _ in range(t):
        k = int(input())
        print(result[k % PERIOD])

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：预处理 + 模运算
  • 时间复杂度：预处理 ，查询
  • 空间复杂度： - 只需要存储150个数