题解|信息学奥赛一本通-提高篇 Fibonacci

思路

矩阵加速递推基础题.
因为 $f_i=f_{i-1}+f_{i-2}(i>2)$ ,可以构造出矩阵.

$\left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f_{i-1}\\ f_{i-2} \end{matrix} \right]= \left[ \begin{matrix} f_{i}\\ f_{i-1} \end{matrix} \right]$
$\left[ \begin{matrix} f_n\\ f_{n-1} \end{matrix} \right]= \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right]^{n-2} \left[ \begin{matrix} f_2 \\ f_1 \end{matrix} \right]$
然后跑矩阵快速幂即可.代码中的矩阵可能稍微有点不同,毕竟是以前写的代码.不过只要理解矩阵加速递推就没问题了.
由于这是多组数据,一种优化方法是将 $B^{2^i}$ 全部存起来(其中 $B$ 表示递推矩阵).大概可以减少一半的常数.
注意边界问题 $(N\le1)$
复杂度大概为 $O(8T\log N)$

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;

int N, M;

struct mat{
    int a[2][2];
    mat operator * ( mat t ){
        mat r; memset( r.a, 0, 16 );
        fp( i, 0, 1 ) fp( k, 0, 1 ) fp( j, 0, 1 ) r.a[i][j] = ( r.a[i][j] + 1ll * a[i][k] * t.a[k][j] ) % M;
        return r;
    }
}o, t;

int main(){
    t_bg = clock();
    read(N), read(M);
    if ( N <= 2 ) return printf( "%d\n", 1 % M ), 0;
    t.a[0][0] = t.a[0][1] = 1;
    o.a[0][0] = o.a[1][0] = o.a[0][1] = 1;
    for ( int i = N - 2; i; i >>= 1, o = o * o ) if ( i & 1 ) t = t * o;
    printf( "%d\n", t.a[0][0] % M );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}