HDU 1005 Number Sequence（矩阵）

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

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).

Input

The input consists of multiple test cases. Each test
case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1
<= n <= 100,000,000). Three zeros signal the end of input and this test
case is not to be processed.

Output

For each test case, print the value of f(n) on a single
line.

Sample Input

1 1 3
1 2 10
0 0 0

Sample Output

2
5

Author

CHEN, Shunbao

Source

ZJCPC2004

Recommend

JGShining   |   We have carefully selected several
similar problems for you:  1008 1004 1021 1019 1002 

这道题需要推一个类似于斐波那契矩阵的矩阵。

比较好推

 #include<cstdio>
 #include<cstring>
 #include<iostream>
 using namespace std;
 const int MAXN=;
 inline void read(int &n){char c='+';bool flag=;n=;
 while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
 while(c>=''&&c<='') n=n*+c-,c=getchar();flag==?n=-n:n=n;}
 struct matrix
 {
     int m[][];matrix(){memset(m,,sizeof(m));}
 };
 matrix ma;
 int limit=;
 const int mod=;
 matrix mul(matrix a,matrix b)
 {
     matrix c;
     for(int k=;k<limit;k++)
         for(int i=;i<limit;i++)
             for(int j=;j<limit;j++)
                 c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod;
     return c;
 }
 matrix fast_martix_pow(matrix ma,int p)
 {
     matrix bg;
     bg.m[][]=;bg.m[][]=;
     bg.m[][]=;bg.m[][]=;
     /*for(int i=0;i<limit;i++)
     {
         for(int j=0;j<limit;j++)
             cout<<bg.m[i][j]<<" ";
         cout<<endl;
     }*/

     while(p)
     {
         if(p&)    bg=mul(bg,ma);
         ma=mul(ma,ma);
         p>>=;
     }
     return bg;
 }
 int main()
 {
     int a,b,n;
     while(scanf("%d%d%d",&a,&b,&n)&&(a!=&&b!=&&n!=))
     {
         ma.m[][]=a;ma.m[][]=b;
         ma.m[][]=;ma.m[][]=;
         if(n<)
         {
             printf("1\n");
             continue;
         }
         matrix ans=fast_martix_pow(ma,n-);
         printf("%d\n",(ans.m[][]+ans.m[][])%mod);
     }
     return ;
 }