递推转矩阵快速求幂算法

以你之姓@ 2023-10-05 13:38 64阅读 0赞

## 例：给定数列1，1，1，1，3，5，9，17，···，从第4项开始，每项都是前3项的和。求第20202020项的最后4位数是多少。 ##

本问题的思路是将数列的求项问题转化为矩阵求幂问题

#include<iostream>
    #include<ctime>
    using namespace std;
    int base[3][3] = {
         0,1,0, 0,0,1, 1,1,1 };  //底数矩阵
    int res[3][3] = {
         1,0,0 ,0,1,0 ,0,0,1 };  //结果矩阵
    void sqr() {
        
    	int temp[3][3];
    	for (int i = 0; i < 3; i++)
    		for (int k = 0; k < 3; k++) {
        
    			temp[i][k] = (base[i][0] * base[0][k] + base[i][1] * base[1][k] +base[i][2] * base[2][k])%10000;
    		}
    	for (int i = 0; i < 3; i++)
    		for (int k = 0; k < 3; k++) {
        
    			base[i][k]=temp[i][k] ;
    		}
    }
    void mul() {
        
    	int temp[3][3];
    	for (int i = 0; i < 3; i++)
    		for (int k = 0; k < 3; k++) {
        
    			temp[i][k]=(res[i][0]*base[0][k]+res[i][1] * base[1][k]+res[i][2] * base[2][k])%10000;
    		}
    
    	for (int i = 0; i < 3; i++)
    		for (int k = 0; k < 3; k++) {
        
    			res[i][k] = temp[i][k];
    		}
    
    }
    
    int main(){
        
    
    	int array[3] = {
         1,1,1 }; //初始数组
    	long long n;		//数列第n项
    	long long exp;  //次幂
    	cin >> n;
    	exp = n - 3;
    	clock_t start = clock();
    	while (exp >= 1) {
        
    
    		if (exp % 2 == 1)		//如果次幂为奇数则要先分离即底数要先与结果相乘
    			mul();
    		if (exp != 1)			//如果次幂为1，则无需对底数进行平方
    			sqr();
    		exp = exp / 2;
    	}
    	clock_t end = clock();
    	cout << (end - start) << "ms" << endl;
    
    	//矩阵输出
    	for (int i = 0; i < 3; i++) {
        
    		for (int k = 0; k < 3; k++)
    			cout <<res[i][k]<<" ";
    		cout << endl;
    	}
    	//因为初始数组值全为1，所以可以直相加
    	cout << (res[2][0] + res[2][1] + res[2][2] )%10000<< endl;
    	
    	return 0;		
    }