P1349 Generalized Fibonacci sequence

Generalized Fibonacci Sequence#

Problem Description#

The generalized Fibonacci sequence is defined as a sequence of the form $a_n=p\times a_{n-1}+q\times a_{n-2}$ .

Given the coefficients $p$ and $q$ of the sequence, as well as the first two terms $a_1$ and $a_2$ , and two integers $n$ and $m$ , find the remainder of the $n$ th term $a_n$ modulo $m$ .

Input Format#

The input consists of a single line containing six integers: $p,q,a_1,a_2,n,m$ .

Output Format#

The output consists of a single line containing an integer representing the answer.

Example #1#

Input Example #1#

1 1 1 1 10 7

Output Example #1#

Hint#

The 10th term of the sequence is 55, and $55 \bmod 7 = 6$ .

【Data Range】
For 100% of the data, $p,q,a_1,a_2 \in [0,2^{31}-1]$ , and $1\le n,m \le 2^{31}-1$ .

Problem Analysis#

The problem requires the value of $a_n\%m$ .

To solve this, we need to find the nth term and then take the remainder. The problem already provides the recursive formula $a_n=p\times a_{n-1}+q\times a_{n-2}$ . A brute force approach would be to start from the 3rd term and enumerate each term until the nth term is reached. The time complexity of this approach is $O(n)$ . However, the data range of this problem is large, and the brute force approach will exceed the time limit. Therefore, we need to accelerate the process of finding the nth term.

To accelerate the recursive process, we can try using matrix exponentiation.

Let matrix A be: [ $a_{n-2}\ a_{n-1}$ ].

\begin{bmatrix} a_{n-2} & a_{n-1} \end{bmatrix} \times \begin{bmatrix} b_{1,1} & b_{1,2} \\ b_{2,1} & b_{2,2} \\ \end{bmatrix} = \begin{bmatrix} a_{n-1} & a_{n} \end{bmatrix}

This means that

a_{n-2}\times b_{1,1}+a_{n-1}\times b_{2,1}=a_{n-1}\\ a_{n-2}\times b_{1,2}+a_{n-1}\times b_{2,2}=a_n

Combining this with the recursive formula $a_n=p\times a_{n-1}+q\times a_{n-2}$ , we can deduce that the acceleration matrix B is

\begin{bmatrix} 0 & q \\ 1 & p \\ \end{bmatrix}

We can observe that each multiplication of matrix B corresponds to moving one term forward. Therefore, finding the nth term becomes finding the first column of $A\times B^{n-1}$ , and we can use matrix exponentiation to solve it in $O(\log n)$ time complexity.

Code Implementation#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q,a1,a2,n,M;
struct matrix{ll m[5][5];};

matrix operator *(const matrix &a,const matrix &b){
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;
    return c;
}
matrix fastPow(matrix a,int n){
    matrix ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=1;i<=2;i++) ans.m[i][i]=1;
    while(n){
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int main(){
    matrix a,b;
    memset(a.m,0,sizeof(a.m));
    memset(b.m,0,sizeof(b.m));
    cin>>p>>q>>a1>>a2>>n>>M;
    a.m[1][1]=a1;a.m[1][2]=a2;
    b.m[1][1]=0;b.m[1][2]=q;
    b.m[2][1]=1;b.m[2][2]=p;
    matrix c=a*fastPow(b,n-1);
    cout<<c.m[1][1];
    return 0;
}