M_sea

洛谷1349 广义斐波那契数列
题目描述广义的斐波那契数列是指形如$a_n=p*a_{n-1}+q*a_{n-2}$的数列。今给定数列的两系数$p...
扫描右侧二维码阅读全文
03
2018/08

洛谷1349 广义斐波那契数列

题目描述

广义的斐波那契数列是指形如$a_n=p*a_{n-1}+q*a_{n-2}$的数列。今给定数列的两系数$p$和$q$,以及数列的最前两项$a_1$和$a_2$,另给出两个整数$n$和$m$,试求数列的第$n$项$a_n$除以$m$的余数。

传送门

算法

我们要从状态$f[i-1],f[i-2]$,推至状态$f[i],f[i-1]$。

那么因为:

$$f[i]=f[i-1]*p+f[i-2]*q$$

$$f[i-1]=f[i-1]*1+f[i-2]*0$$

所以构造出矩阵:

p 1
q 0

上模板即可。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int MOD; 

struct Matrix {
    int x,y;
    int m[10][10];
};

Matrix Mul(Matrix a,Matrix b) {
    Matrix c; c.x=a.x,c.y=b.y;
    for (re int i=1;i<=a.x;i++)
        for (re int j=1;j<=b.y;j++) {
            c.m[i][j]=0;
            for (re int k=1;k<=a.y;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
        }
    return c;
}

Matrix FastPow(Matrix a,int k) {
    Matrix rt;
    rt.x=rt.y=a.x;
    for (re int i=1;i<=a.x;i++) //构造单位矩阵 
        for (re int j=1;j<=a.y;j++)
            rt.m[i][j]=(i==j);
    while (k) {
        if (k&1) rt=Mul(rt,a);
        a=Mul(a,a);
        k>>=1;
    }
    return rt;
}

Matrix A,B;

mainint main() {
    int p=read(),q=read();
    A.m[1][2]=read(),A.m[1][1]=read();
    int S=read(); MOD=read();
    if (S<=2) { printf("%lld\n",A.m[1][S]); return 0; }
    
    A.x=1,A.y=2,B.x=2,B.y=2;
    B.m[1][1]=p,B.m[1][2]=1,B.m[2][1]=q,B.m[2][2]=0;
    
    A=Mul(A,FastPow(B,S-2));
    printf("%lld\n",A.m[1][1]%MOD);
    return 0;
}
最后修改:2018 年 11 月 10 日 08 : 32 PM

发表评论