HDU5667 Sequence

First attach the title link

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

Topic analysis

Problems like this recursive formula ,n Very big time , The common processing method is matrix fast power , But this seems difficult to construct .

Bloggers' ideas are as follows ： Take the logarithm set up k(i) = loga(f(i))

that According to the derivation
k(1) = loga(1)=0
k(2) = loga(a^b) = b
k(i) = b + c*k(i-1)+k(i-2)
Then we can use the method of matrix fast power solve k(n) f(n) = a^k(n) Then solve by integer fast power .
There's another problem ：k(n) It's big Direct exponentiation must be connected int64_t Will overflow Then use Fermat's small Theorem

a^p-1=== 1 mod p

That is ：a^p-1=== a⁰ mod p So the cyclic section is p-1, We can pass the k(n)%(p-1) Calculate the minimum remainder

therefore f(n) = a^(k(n)) = a^(k(n)%(p-1))%p
So the remainder operator of the fast power of the matrix is also obtained

Next, calculate the transfer matrix

Let the transition matrix be T, The initial matrix is K
K ={ k(2), k(1), 1}^T={b,0,1}^T

Then the transfer matrix T =

Matix T = {
    
	c,1,b,
	1,0,0,
	0,0,1
};

T*K The top right element of is k(3) that T^(n-2)*K The top right element of is k(n).

Matrix structure

const int N = 3;
typedef struct Matix{
    
	int64_t m[N][N];
}Matix;

Matrix multiplication

// Matrix multiplication 
Matix temp;
Matix Matix_Mutiply(Matix a,Matix b){
    
	memset(temp.m,0,sizeof(temp.m));// Initialization matrix temp
	for(int i=0;i<N;i++){
    
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
			temp.m[i][j] = (temp.m[i][j] + a.m[i][k]*b.m[k][j]%MOD)%MOD;//MOD = p-1  Assignment in the main function 
	}
	return temp;
}

Matrix fast power

// Matrix fast power 
Matix C,d;// Define a unit matrix 
Matix Matix_Pow(Matix a,int64_t n){
    
	memset(C.m,0,sizeof(C.m));d = a;// So as not to a It's gone 
	for(int i=0;i<N;i++) C.m[i][i] = 1;// The unit matrix is defined 
	while(n){
    
		if(n & 1) C = Matix_Mutiply(C,d); //C = C*d;
		d = Matix_Mutiply(d,d);
		n = n>>1;
	}
	return C;
}

Fast exponentiation of integers

// Fast exponentiation of integers 
int64_t fastpow(int64_t a,int64_t n){
    
	int64_t ans = 1,tp = a;
	if(n==0) return ans;
	while(n){
    
		if(n&1) ans = ans*tp%p;
		tp = tp*tp%p;
		n = n>>1;
	}
	return ans;
}

Through the above algorithm Get f(n) = a^(k(n)) = a^(k(n)%(p-1))%p

AC Code

//32802364 2020-03-18 00:52:56 Accepted 5667 31MS 1416K 1679 B G++ sharpcoder
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<inttypes.h>
using namespace std;
const int N = 3;// All squares in this question are 3 Dimensional 
int64_t n,a,b,c,p;
int64_t MOD;//MOD = p-1;
typedef struct Matix{
    
	int64_t m[N][N];
}Matix;
// Matrix multiplication 
Matix temp;// Global variables can reduce spatial complexity 
Matix Matix_Mutiply(Matix a,Matix b){
    
	memset(temp.m,0,sizeof(temp.m));// Initialization matrix temp
	for(int i=0;i<N;i++){
    
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
			temp.m[i][j] = (temp.m[i][j] + a.m[i][k]*b.m[k][j]%MOD)%MOD;
	}
	return temp;
}
// Matrix fast power 
Matix C,d;// Define a unit matrix 
Matix Matix_Pow(Matix a,int64_t n){
    
	memset(C.m,0,sizeof(C.m));d = a;// So as not to a It's gone 
	for(int i=0;i<N;i++) C.m[i][i] = 1;// The unit matrix is defined 
	while(n){
    
		if(n & 1) C = Matix_Mutiply(C,d); //C = C*d;
		d = Matix_Mutiply(d,d);
		n = n>>1;// Move right   Equivalent to n = n/2;
	}
	return C;
}
// Fast exponentiation of integers 
int64_t fastpow(int64_t a,int64_t n){
    
	int64_t ans = 1,tp = a;
	if(n==0) return ans;
	while(n){
    
		if(n&1) ans = ans*tp%p;
		tp = tp*tp%p;
		n = n>>1;
	}
	return ans;
}
int main(){
    
	int t;cin>>t;// Altogether t Group test sample 
	while(t--){
    
		cin>>n>>a>>b>>c>>p;// Enter n,a,b,c,p
		MOD = p-1;// Don't forget this sentence 
		Matix K = {
        // transition matrix 
			c,1,b,
			1,0,0,
			0,0,1
		};
		if(n==1){
    
			cout<<1<<endl;
			continue;
		}else if(n==2){
    
			cout<<fastpow(a,b)<<endl;
			continue;
		}
		// After taking the logarithm  T(1) = loga 1 = 0;T(2) = loga a^b = b;
		Matix T = {
       // The initial matrix 
			b,0,0,
			0,0,0,
			1,0,0
		};
		K = Matix_Pow(K,n-2);// Find n-2 The next power 
		//T = Matix_Mutiply(K,T);
		//T(n) = K^(n-2)*T1
		T.m[0][0] = K.m[0][0]*b + K.m[0][1]*0 + K.m[0][2]*1;//T.m[0][0] Is defined above k(n)
		cout<<fastpow(a,T.m[0][0])<<endl;
	}
	return 0;
}