题解 | #数列#

#include <iostream>
#include <vector>
using namespace std;

//迭代写法，用例测试过多时会超时
int series(int n){
    if(n==1)
        return 1;

    int n1=1;
    int n2=0;
    int k=2;
    int res=2;
    while(k<=n){
        res=(2*n1+n2)%32767;
        n2=n1;
        n1=res;
        k++;
    }
    return res;
}

int main() {
    int n=0;
    vector<int> res={1,2};
    res.reserve(1000000);
    for(int i=2;i<res.capacity();i++){
        res.push_back(res[i-1]*2+res[i-2]);
        /*
        这里运用取模的性质防止答案溢出
        an=2*an-1+an-1
        res=an%32767=2*an%32767+an-1%32767
        */
        res[i]=res[i]%32767;
    }
    cin>>n;
    while (n) { // 注意 while 处理多个 case
        int k;
        cin>>k;
        cout<<res[k-1]<<endl;
        n--;
    }
}
// 64 位输出请用 printf("%lld")