codevs 3332 数列 （矩阵乘法）

时间：2023-03-08 22:03:08
/*

裸地矩阵乘法

矩阵很好想的

1 1 0

0 0 1

1 0 0

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#define mod 1000000007

#define ll long long

using namespace std;

int T,n;

ll f[][],a[][];

void mul(ll a[][],ll b[][])

{

    ll c[][];

    memset(c,,sizeof(c));

    for(int i=;i<=;i++)

      for(int j=;j<=;j++)

        for(int k=;k<=;k++)

          c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;

    for(int i=;i<=;i++)

      for(int j=;j<=;j++)

        a[i][j]=c[i][j];

}

int main()

{

    scanf("%d",&T);

    while(T--)

      {

          memset(f,,sizeof(f));

          memset(a,,sizeof(a));

          a[][]=;a[][]=;a[][]=;a[][]=;f[][]=;f[][]=;

          scanf("%d",&n);

          if(n<=)

            {

                printf("1\n");

                continue;

          }

          n-=;

          while(n)

            {

                if(n&)mul(f,a);

                mul(a,a);

                n>>=;

          }

        printf("%ld\n",f[][]);

      }

    return ;

}

相关文章