1189：Pell数列（递推）

问题描述：

1189：Pell数列

【题目描述】
Pell数列a1,a2,a3,…的定义是这样的，a1=1,a2=2,…,an=2an−1+an−2(n>2)。

给出一个正整数k，要求Pell数列的第k项模上32767是多少。

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

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

【输入样例】
2
1
8
【输出样例】
1
408

问题分析：

此题和1188：菲波那契数列(2)，属于同类型题；
直接定义一个大数组，存所有项的Pell数列的值，由于后面项可能数值比较大，所以每次存入数组时，对32767求余，即可解决该问题，最后直接输出b数组存的第a[i]位的值

解决方案：

#include <bits/stdc++.h>
using namespace std;
int b[1000001]; //提前计算出数列每一项的值 
int main() {
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++) {
		cin>>a[i];
	}
	b[0]=1;
	b[1]=2;
	//计算数列 
	for(int i=2; i<=1000000; i++) {
		b[i]=(2*b[i-1]+b[i-2])%32767;//利用高精度思想，每次计算后都取模 
	}
	for(int i=0; i<n; i++) {
		cout<<b[a[i]-1]<<endl;//输出第i位的值，由于数列下标从0开始，要减1 
	}
}