矩阵快速幂的总结

矩阵乘法：(方阵n*n)

struct stu{
    int arr[3][3];
};
stu mul(stu x,stu y){//这里一定是x  ×  y不能相反 
    stu a;
    memset(a.arr,0,sizeof(a.arr));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                a.arr[i][j]=(a.arr[i][j]%mod+x.arr[i][k]*y.arr[k][j]%mod )%mod;
    return a;
}

矩阵快速幂：（类似与快速幂运算）：（注意返回值也是一个结构体‘’

stu ksm(stu aa,int  b){
    
    stu res;
    memset(res.arr,0,sizeof(res.arr));
    for(int i=0;i<2;i++)
        res.arr[i][i]=1;
     
    while(b){
        if(b&1) res=mul(res,aa);
        aa=mul(aa,aa);
        b>>=1;
    }
    
    return res;
}

矩阵快速幂的几种类型题目

矩阵快速幂的总结

http://acm.hdu.edu.cn/showproblem.php?pid=5950

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and . Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b <

as described above.

Output

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

Sample Input

2 3 1 2 4 1 10

Sample Output

85 369

Hint

In the first case, the third number is 85 = 2*1十2十3^4. In the second case, the third number is 93 = 2*1十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=2147493647;

struct stu{
    ll arr[10 ][10 ];
};

stu mul(stu x,stu y){
    stu xx;
    memset(xx.arr,0,sizeof(xx.arr));
    for(int i=0;i<7;i++)
        for(int j=0;j<7;j++)
            for(int k=0;k<7;k++)
                xx.arr[i][j]=(xx.arr[i][j]%mod+x.arr[i][k]*y.arr[k][j]%mod)%mod;
    return xx;
}

stu ksm(stu x,ll b){
    stu res;
    memset(res.arr,0,sizeof(res.arr));
    for(int i=0;i<7;i++){
        res.arr[i][i]=1;
    }
    while(b){
        if(b&1) res=mul(res,x);
        x=mul(x,x);
        b>>=1;
    }
    return res;
}


int main(){
    int t;
    cin>>t;
    while(t--){
         ll n,a,b;
         cin>>n>>a>>b;
         stu arr1,arr2;
         memset(arr1.arr,0,sizeof(arr1.arr));
         arr1.arr[0][0]=1,arr1.arr[0][1]=2,arr1.arr[0][2]=1;
         arr1.arr[1][0]=1;
         arr1.arr[2][2]=1,arr1.arr[2][3]=4,arr1.arr[2][4]=6,arr1.arr[2][5]=4,arr1.arr[2][6]=1;
         arr1.arr[3][3]=1,arr1.arr[3][4]=3,arr1.arr[3][5]=3,arr1.arr[3][6]=1;
         arr1.arr[4][4]=1,arr1.arr[4][5]=2,arr1.arr[4][6]=1;
         arr1.arr[5][5]=1,arr1.arr[5][6]=1;
         arr1.arr[6][6]=1;
         memset(arr2.arr,0,sizeof(arr2.arr));
         arr2.arr[0][0]=b,arr2.arr[1][0]=a;
         for(int i=2;i<7;i++){
             arr2.arr[i][0]=pow(3,6-i);
         }
         stu ans;
         if(n==1) cout<<a<<endl;
         else if(n==2) cout<<b<<endl;
         else{
             ans=ksm(arr1,n-2);
             ans=mul(ans,arr2);
             cout<<(ans.arr[0][0])%mod<<endl;
        }
    }
    return 0;
}

这种类型的题目属于递推加+n^4的题目

做法就是先将n+1的四次方拆开,,对他的每一项用矩阵运算开始凑

1 2 1 0 0 0 0 　　 f[i-1]　　　　　　　　f[i]

1 0 0 0 0 0 0 　　 f[i-2]　　　　　　　　f[i-1]　　

0 0 1 4 6 4 1　　　　i^4　　　　　　　　 (i+1)^4

0 0 0 1 3 3 1 * 　i^3 = (i+1)^3

0 0 0 0 1 2 1　　　　i^2　　　　　　　　 (i+1)^2

0 0 0 0 0 1 1　　　　i　　　　　　　　　 i+1

0 0 0 0 0 0 1　　　 1　　　　　　　　　 1　　

然后构造矩阵就可以了

相关推荐