UVA10229 Modular Fibonacci 题解

RP_INT_MAX · 2023-03-19 22:31:24 · 题解

矩阵乘法板题。难度虚高了。

\tt Solution

以下设斐波那契数列第 i 项为 f_i。

很显然题目求的就是 f_n \bmod 2^m 的值。n,m 不大，直接矩阵快速幂取模即可。

考虑构造矩阵 A 使得 f_i = A \times f_{i-1}。

列出递推式子：

f_{i}=1 \times f_{i-1}+1 \times f_{i-2}
f_{i-1}=1 \times f_{i-1}+0 \times f_{i-2}

故构造矩阵：

A=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}

\tt Code

#include <cstdio>
using namespace std;
typedef long long ll;
ll n,m,Mod;
struct M{ll m[2][2];};
M mul(M A,M B) {
    M C;
    for(int i=0;i^2;++i)
        for(int j=0;j^2;++j) {
            C.m[i][j]=0;
            for(int k=0;k^2;++k) (C.m[i][j]+=A.m[i][k]*B.m[k][j])%=Mod;
        }
    return C;
}
M qp(M A,ll k) {
    M C={};
    for(int i=0;i^2;++i) C.m[i][i]=1;
    while(k) {
        if(k&1) C=mul(C,A);
        A=mul(A,A);
        k>>=1;
    }
    return C;
}
int main () {
    while(~scanf("%lld%lld",&n,&m)) {
        if(!n) {puts("0");continue;}
        Mod=1LL<<m;
        M x={1,1,1,0};
        M ans=qp(x,n-1);
        printf("%lld\n",ans.m[0][0]);
    }
    return 0;
}