见 此笔记 第0部分。

题目链接

题意

$$ n\leq 2,F(n)=1. \\ n>2,F(n)=F(n-1)+F(n-2). $$

对于上述递推式，求 $F(n)\mod 1e9+7$ ，给出的 $n\leq 2^{63}$ .

思路

递推式给你了。照理讲 $O(n)$ 是多么优秀的复杂度啊 然而并不。

于是，对于一个清晰明白的递推式，考虑矩乘。

当然你要上生成函数也没人拦你，不过有一说一斐波那契的生成函数不咋好看（

首先是答案矩阵：
$$ F(n)= \begin{pmatrix} f(n) & f(n-1)\\ \end{pmatrix} $$
然后是转移矩阵。转移矩阵 $base$ 可以通过：
$$ F(n)\times base=F(n+1) $$
来确定。保险一点就是设出每个矩阵中的数，然后根据每个项解方程即可 当然也可以看着递推式直接手推 。

但是我个人比较喜欢通过矩阵意义推理。

首先，根据矩阵乘法 c[i][j]=a[i][k]*b[k][j] ，可以知道, $base$ 的第一行就是 $F(n)$ 第一列也就是 $f(n)$ 对下一个答案矩阵的两列的贡献。

具体地讲，$base$ 的第一行就是 $f(n)$ 分别对 $F(n+1)$ 中 $f(n+1)$ （第一列）和 $f(n)$ （第二列）贡献了 $1\times f(n)$ .$f(n-1)$ 同理。

最后的 $base$ :
$$ \begin{pmatrix} 1 & 1\\\\ 1 & 0\\\\ \end{pmatrix} $$

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;

struct matrix
{
        ll mt[5][5];
        matrix() { memset(mt,0,sizeof(mt)); }
        matrix  operator * ( matrix b )
        {
                matrix c;
                for ( int i=1; i<=2; i++ )
                 for ( int j=1; j<=2; j++ )
                  for ( int k=1; k<=2; k++ )
                        c.mt[i][j]=(c.mt[i][j]+(mt[i][k]*b.mt[k][j])%mod)%mod;
                return c;
        } 
}ans,base;

matrix power( ll b )
{
        matrix res=ans,a=base;
        for ( ; b; b>>=1,a=a*a )
                if ( b&1 ) res=res*a;
        return res;
}

int main()
{
        ll n; scanf( "%lld",&n );
        if ( n<=2 ) { printf( "1\n"); return 0; }
        ans.mt[1][1]=1; ans.mt[1][2]=1; ans.mt[2][1]=0; ans.mt[2][2]=0;
        base.mt[1][1]=1; base.mt[1][2]=1; base.mt[2][1]=1; base.mt[2][2]=0;
        ans=power(n-2);
        printf( "%lld\n",ans.mt[1][1] );
}

AcWing 版本代码如下：

#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
const int mod=10000;
int n;

void chengself( int a[2][2] )   //计算“常数”矩阵的幂次（中的乘法)
{
    int c[2][2]={0};
    for ( int i=0; i<2; i++ )
     for ( int j=0; j<2; j++ )
      for ( int k=0; k<2; k++ )
        c[i][j]=(c[i][j]+(ll)(a[i][k]*a[k][j])%mod)%mod;
    memcpy( a,c,sizeof(c) );
} 

void cheng( int f[2],int a[2][2] )  //Fibonacci的初始数组*常数幂 
{
    int c[2]={0};
    for ( int j=0; j<2; j++ )
     for ( int k=0; k<2; k++ )
        c[j]=(c[j]+(ll)(f[k]*a[k][j])%mod)%mod;
    memcpy( f,c,sizeof(c) );
}

int main()
{
    while ( scanf( "%d",&n ) && n>=0 )
    {
        if ( n==0 ) 
        {
            printf( "0\n" ); continue;
        }
        int f[2]={0,1},a[2][2]={{0,1},{1,1}};
        for ( ; n; n>>=1 )
        {
            if ( n&1 ) cheng( f,a );
            chengself( a );
        }

        printf( "%d\n",f[0] );
    }
}