Demo entry 6346112

c++

   

Submitted by anonymous on Feb 09, 2017 at 17:00
Language: C++. Code size: 1.5 kB.

#include<set> 
#include<stack>
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<b;i++)
#define rec(i,a)   for(i=0;i<a;i++)
#define N 10000  +  10
#define Q 1000   +  10
#define P 100    +  1
struct matrix
{
    int a[15][15];
};
matrix mat1;
matrix mat2;
matrix function(matrix mat1,matrix mat2,int mod)
{
    int i,j,k;
    matrix T;
    memset(T.a,0,sizeof T.a);
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            for(k=0;k<2;k++)
            {
                T.a[i][j]=(T.a[i][j]+mat1.a[i][k]*mat2.a[k][j]%mod)%mod;
            }
        }
    }
    return T;
    memset(T.a,0,sizeof T.a);
}
int main()
{
      int A,B;
    __int64 n;
    __int64 mod=7;
      while(scanf("%d%d%I64d",&A,&B,&n)==3)
      {
          if(A==0&&B==0&&n==0)break;
          mat1.a[0][0]=A;mat2.a[0][0]=A;
          mat1.a[0][1]=B;mat2.a[0][1]=B;
          mat1.a[1][0]=1;mat2.a[1][0]=1;
          mat1.a[1][1]=0;mat2.a[1][1]=0;
          if(n==1||n==2)
          {
              printf("1\n");
          }
          else
          {
              n=n-3;
              while(n!=0)
              {
                  if(n&1)
                  mat1=function(mat1,mat2,mod);
                  mat2=function(mat2,mat2,mod);
                  n>>=1;
              }
              printf("%d\n",(mat1.a[0][0]+mat1.a[0][1])%mod);
          }
      }
return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).