Pell数列a_1,a_2,a_3,...a_1,a_2,a_3,...的定义是这样的，a_1=1,a_2=2,...,a_n=2a_n−1+a_n−2(n>2)a_1=1,a_2=2,...,a_n=2a_n−1+a_n−2(n>2)。

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

输入

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

输出

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

样例

输入数据 1

2
1
8

 

输出数据 1

1
408

 思路：减少运行时间：

1.用<记录数组>存储数据，不在每次输入k时重新循环，而是在一次循环后可以在数组对应位置直接调用对应索引处的数据（动态规划）

2.记录k的最大值max，若新输入的k小于max，则不再重新生成<记录数组>max索引位置及以前的数据，并且不生成max之后的数据

3.在每次得出一个数据后直接取余        与每次运算不取余，算出最终结果后再取余所得余数相同，因为冗余的可以被32767除去的数什么时候除都行

#include <iostream>
using namespace std;
int arr[1000000] = {0,1,2};
int main()
{int n = 0,k = 0,max =-1;cin >> n;for (int i = 1; i <= n; i++){cin >> k;if(max<k){max = k;for (int j = 1; j <= max; j++){if (j >= 3)arr[j] = (2 * arr[j - 1] + arr[j - 2]) % 32767;}}cout << arr[k] << endl;}return 0;
}