一本通1642【例 2】Fibonacci 第 n 项

1642： 【例 2】Fibonacci 第 n 项

sol：挺模板的吧，经典题吧qaq

（1）

1 0    *     1 1     =   1 1

1 0

（2）

1 1    *     1 1     =   2 1

1 0

（3）

2 1    *     1 1     =   3 2

1 0

所以第n项就是1 0 *       (1,1)

(1,0)

用快速幂优化就是矩阵快速幂了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+'');    return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

/*

1 0     1 1

        1 0

*/

ll n,Mod;

ll a[][],b[][],ans[][],c[][];

inline void Ad(ll &X,ll Y)

{

    X=X+Y;

    X-=(X>=Mod)?Mod:;

    return;

}

int main()

{

    int i,j,k;

    n=read()-; R(Mod);

    a[][]=a[][]=a[][]=; a[][]=;

    ans[][]=ans[][]=; ans[][]=ans[][]=;

    while(n)

    {

        if(n&)

        {

            memset(c,,sizeof c);

            for(i=;i<=;i++)

            {

                for(j=;j<=;j++)

                {

                    for(k=;k<=;k++) Ad(c[i][j],ans[i][k]*a[k][j]%Mod);

                }

            }

            memmove(ans,c,sizeof ans);

        }

        memset(c,,sizeof c);

        for(i=;i<=;i++)

        {

            for(j=;j<=;j++)

            {

                for(k=;k<=;k++) Ad(c[i][j],a[i][k]*a[k][j]%Mod);

            }

        }

        memmove(a,c,sizeof a);

        n>>=;

    }

    b[][]=; b[][]=;

    memset(c,,sizeof c);

    for(i=;i<=;i++)

    {

        for(j=;j<=;j++)

        {

            for(k=;k<=;k++) Ad(c[i][j],ans[i][k]*b[k][j]);

        }

    }

    memmove(b,c,sizeof b);

    Wl(b[][]);

    return ;

}

/*

input

5 1000

output

5

*/