Number Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 147964 Accepted Submission(s): 35964

Problem Description

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Sample Input

1 1 3

1 2 1

0
0 0 0

Sample Output

因为数据量比较大，可以打表找到循环规律，但这种类型的题发现都可以构造矩阵求解

f[n]　　　　　　= a b * f[n-1]

f[n-1] 1 0　　 f[n-2]

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int a,b,n;

 int m[];

 struct Matrix

 {

     int mat[][];

 }p;

 Matrix mul(Matrix a,Matrix b)

 {

     Matrix c;

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

     {

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

         {

             c.mat[i][j]=;

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

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

         }

     }

     return c;

 }

 Matrix mod_pow(Matrix x,int n)

 {

     Matrix res;

     memset(res.mat,,sizeof(res.mat));

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

         res.mat[i][i]=;

     while(n)

     {

         if(n&)

             res=mul(res,x);

         x=mul(x,x);

         n>>=;

     }

     return res;

 }

 int main()

 {

     freopen("in.txt","r",stdin);

     while(scanf("%d%d%d",&a,&b,&n)!=EOF)

     {

         if(a==&&b==&&n==)

             break;

         if(n<)

         {

             printf("1\n");

             continue;

         }

         p.mat[][]=a;

         p.mat[][]=;

         p.mat[][]=b;

         p.mat[][]=;

         Matrix ans= mod_pow(p,n-);

         printf("%d\n",(ans.mat[][]+ans.mat[][])%);

     }

 }

构造矩阵

Number Sequence(HDU 1005 构造矩阵 )

Number Sequence