#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
    cin>>n;
    long long b[1000000];
    b[1]=1;
    b[2]=2;
    for(int i=3;i<1000000;i++){
        b[i]=(2*b[i-1]+b[i-2])%32767;
    }
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        cout<<b[x]<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k,Pell[1000005];

    Pell[0] = 1;
    Pell[1] = 2;

    for(int a=2;a<1000000;a++){
        Pell[a] = (Pell[a-1] * 2 + Pell[a-2]) % 32767;
    }

    cin>>n;

    for(int i=0;i<n;i++){
        cin>>k;
        cout<<Pell[k-1]<<endl;
    }

    return 0;
}

56.Pell数列Ⅱ(广赋张老师的题解）

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[1000001];//提前计算好Pell数列保存到数组a
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=1000001;i++){//每项=前1项的两倍+前2项
        a[i] = (2*a[i-1]+a[i-2])%32767;
        //cout<<a[i]<<' ';
    }
    int n,k;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        cout<<a[k]<<endl;
    }

    return 0;
}

#include<bits/stdc++.h> using namespace std; int n,k; int main(){ ios::sync_with_stdio(false); cin.tie(0); vector v(1000005); v[1]=1; v[2]=2; cin>>n; while(n--){ cin>>k; for(int i=3;i<=k;i++){ v[i]=(2*v[i-1]+v[i-2])%32767; } cout<<v[k]<<"\n"; } return 0; }

#include<bits/stdc++.>
using namespace std;
int main() {
    int n;
    cin>>n;
    long long b[1000000];
    b[1]=1;
    b[2]=2;
    for(int i=3;i<1000000;i++){
        b[i]=(2*b[i-1]+b[i-2])%32767;
    }
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        cout<<b[x]<<endl;
    }

    return 0;
}