思路

近百万下标的Pell递推及过程取模，避免指数递归。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;vector<int>q(t);int m=2;for(int &x:q){cin>>x;m=max(m,x);}vector<int>a(m+1);a[1]=1;a[2]=2;for(int i=3;i<=m;i++)a[i]=(2*a[i-1]+a[i-2])%32767;for(int x:q)cout<<a[x]<<'\n';}