题⽬描述

    Pell数列的定义是a[1]=1,a[2]=2,......,a[n]=2*a[n-1]+a[n-2] (n>2),给出正整数k，求第k项模32764是多少

输⼊格式

    第一行一个整数n表示组数。 后n行（0≤n≤5），每组包括一个正整数k

输出格式 输出n个整数表示答案

#include<bits/stdc++.h>
using namespace std;
long long read()
{
    long long x=0,t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')t=-t;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*t;
}
int mo=32764;
struct VECTOR{int v[2];};
struct MATRIX{VECTOR m[2]={(VECTOR){1,0},(VECTOR){0,1}};};
VECTOR operator * (MATRIX a,VECTOR b)
{return (VECTOR){{(a.m[0].v[0]*b.v[0]+a.m[1].v[0]*b.v[1])%mo,(a.m[0].v[1]*b.v[0]+a.m[1].v[1]*b.v[1])%mo}};}
MATRIX operator * (MATRIX a,MATRIX b)
{
    MATRIX res;res.m[0]=a*b.m[0];res.m[1]=a*b.m[1];
    return res;
}
MATRIX ksm(MATRIX a,long long b)
{
    MATRIX tmp=a,res;
    while(b)
    {
        if(b&1)res=res*tmp;
        tmp=tmp*tmp;b>>=1;
    }
    return res;
}
int main()
{
    MATRIX om;VECTOR ov,p;
    p.v[0]=0;p.v[1]=1;om.m[0]=p;p.v[0]=1;p.v[1]=2;om.m[1]=p;ov.v[0]=1;ov.v[1]=2;
    int t=read();
    while(t--)printf("%d\n",(ksm(om,read()-1)*ov).v[0]);
}