Untitled
raw download clone
C
views 54
,
size 1543 b
#include<stdio.h>
#define MOD 1000000007//(unsigned long long)((1e9)+7)

unsigned long long fastpow(unsigned long long *P,unsigned long long exponment)
{
     unsigned long long n = exponment;
     unsigned long long matrice[3][3]={1,2,1,1,0,0,0,1,0},tmp[3][3];
     int i,j;
     while(n)
     {
          if(n&1) //底數乘以次方那坨
          {
               unsigned long long tmp1=P[0],tmp2=P[1],tmp3=P[2];
               for(i=0;i<3;i++)
               {
                    P[i]=((matrice[2-i][0]*tmp3)%MOD+(matrice[2-i][1]*tmp2)%MOD+(matrice[2-i][2]*tmp1)%MOD)%MOD;
               }
          }
          n>>=1;
          for(i=0;i<3;i++)
          {
               for(j=0;j<3;j++)
               {
                    tmp[i][j]=matrice[i][j];
               }
          }
          for(i=0;i<3;i++)
          {
               for(j=0;j<3;j++)
               {
                    matrice[i][j]=((tmp[i][0]*tmp[0][j])%MOD+(tmp[i][1]*tmp[1][j])%MOD+(tmp[i][2]*tmp[2][j])%MOD)%MOD;
               }
          }
     }
     P[2]%MOD;
     if(P[2]<0)P[2]+=MOD;
     return P[2];
}

int main(void)
{
     int t;
     unsigned long long x,P[3];
     scanf("%d",&t);

     while(t--)
     {
          scanf("%lld",&x);
          P[0]=1;P[1]=12;P[2]=13;
          if(x==1)printf("1\n");
          else if(x==2)printf("12\n");
          else if(x==3)printf("13\n");
          else
          {
               printf("%lld\n",fastpow(P,x-3));
          }
     }
     return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.