本文共 1440 字，大约阅读时间需要 4 分钟。

矩阵快速幂，看着听高深，其实就是字面意思，矩阵的快速幂，再说清楚点就是矩阵的幂运算，很好理解，但这涉及到矩阵的乘法，先来矩阵的乘法：上模板：

const int N=2;int tmp[N][N];void multi(int a[][N],int b[][N],int n){    memset(tmp,0,sizeof tmp);    for(int i=0;i
   
    >=1;    }}
   

Let’s define another number sequence, given by the following function: f(0) = a f(1) = b f(n) = f(n − 1) + f(n − 2), n > 1 When a = 0 and b = 1, this sequence gives the Fibonacci Sequence. Changing the values of a and b, you can get many different sequences. Given the values of a, b, you have to find the last m digits of f(n). Input The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integers a b n m. The values of a and b range in [0, 100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4]. Output For each test case, print the last m digits of f(n). However, you should NOT print any leading zero.

Sample Input

4

0 1 11 3

0 1 42 4

0 1 22 4

0 1 21 4

Sample Output

89

4296

7711

946

给定一个斐波那契数列的前两位，求后m位。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define ll long longll mod;const int N=2;int tmp[N][N];void multi(int a[][N],int b[][N],int n){    memset(tmp,0,sizeof tmp);    for(int i=0;i
        
         >=1; }}int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--) { int a,b,m; ll n; cin>>a>>b>>n>>m; mod=1; while(m--) { mod*=10; } if(n==0) { cout<
         
          <
         
        
       
      
     
    
   

转载地址：http://qvyzi.baihongyu.com/