wloving

广義フィボナッチ数列#

問題の説明#

広義のフィボナッチ数列は、$a_n=p\times a_{n-1}+q\times a_{n-2}$という形式の数列を指します。

与えられた数列の 2 つの係数$p$と$q$、および数列の最初の 2 項$a_1$と$a_2$、さらに 2 つの整数$n$と$m$が与えられるので、数列の第$n$項$a_n$を$m$で割った余りを求めてください。

入力の形式#

入力は 1 行で、6 つの整数$p,q,a_1,a_2,n,m$が空白区切りで与えられます。

出力の形式#

出力は 1 行で、答えを表す整数を出力してください。

サンプル #1#

サンプル入力 #1#

1 1 1 1 10 7

サンプル出力 #1#

6

ヒント#

数列の第 10 項は 55 であり、$55 \bmod 7 = 6$です。

【データの範囲】
100% のデータに対して、$p,q,a_1,a_2 \in [0,2^{31}-1]$、$1\le n,m \le 2^{31}-1$です。

問題の分析#

問題では$a_n\%m$の値を求めることが要求されています。

そのため、まず第 n 項を求め、それから余りを取るだけです。問題文では既に再帰の公式$a_n=p\times a_{n-1}+q\times a_{n-2}$が提供されています。暴力的な方法では 3 項目から始めて、項目ごとに列挙して第 n 項まで再帰的に進めば良いです。時間計算量は$O(n)$です。しかし、この問題のデータ範囲は大きいため、直接暴力的な方法では時間切れになる可能性があります。第 n 項を求めるプロセスを高速化する必要があります。

再帰プロセスの高速化のために、行列の高速累乗を試してみることができます。

行列 A を次のように定義します: [$a_{n-2}\ a_{n-1}$]。

これは次のように解釈できます。

再帰式$a_n=p\times a_{n-1}+q\times a_{n-2}$と組み合わせると、高速化行列 B は次のようになります。

わかるように、行列 B を一度掛けるごとに 1 項進めることができます。そのため、第 n 項を求めることは$A\times B^{n-1}$の最初の列の内容を求めることになります。行列の高速累乗を使用することで、$O(\log n)$の時間計算量で解を求めることができます。

コードの実装#

#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;
}