[NOI题库][POJ2786]Pell数列

#include <stdio.h>
#include <string.h>

int a[ 1000010 ];
int n, k;
const int mo = 32767;

int main(){
    scanf("%d", &n);
    
    int last = 3;
    a[ 1 ] = 1;
    a[ 2 ] = 2;
    int i, j;
    for( i = 1; i <= n; i++ ){
        scanf("%d", &k);
        
        for( j = last; j <= k; j++ ){
            a[ j ] = (((2 * a[ j - 1 ]) % mo) + a[ j - 2 ]) % mo;
        }
        if( k > last ) last = k;
        printf("%d\n", a[ k ] % mo);
    }

    return 0;
}