FZU2018级算法第一次作业 1.1fibonacci （矩阵快速幂）

题目

　　winder最近在学习fibonacci 数列的相关知识。我们都知道fibonacci数列的递推公式是f（n）=f（n-1）+f（n-2）（n>=2 且n 为整数）。 winder想知道的是当我们将这个递推式改为f（n）=af（n-1）+bf（n-2）（n>=2且n为整数）时我们得到的是怎样的数列。但是，winder很懒，所以只能由你来帮他来完成这件事。 注意，这里我们依然令f（0）=f（1）=1。

★数据输入

　　输入第一行三个正整数n，a 和b（n<=10；1<=a、b<=100 且均为整数）。 接下来有n 行，每行一个自然数n（n<=100000000）。

★数据输出

　　输出一行一个整数f（n），由于结果可能会很大，winder要求输出结果对2013取模。

输入示例	输出示例
5 4 5 2 4 8 16 32	9 209 1377 182 9

 

题解：

　　一道很经典的矩阵快速幂裸题。

　　首先讲解快速幂，当我们需要求$a^{b}$对mod取模时，可以将b转化为2进制，就可以将b转换为若干个二次幂之和。例如，我们在计算2的12次方时，12的二进制为1100，1100中的两个1的位权分别为4和8，因此$2^{12}$次方便可以转换为$2^{4}*2^{8}$。由此，我们先将答案ans赋值为1，只需要计算a的1，2，4，8.....次方，然后看一下b在该位的数值是否为1即可，如果为1，将ans乘上即可。

快速幂的代码如下

ll fastpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

　　接下来回到本题，由于n的数字较大，加上取模速度较慢，本题递归递推会超时。因此需要寻找复杂度小于o(n)的算法。

　　我们可以构造矩阵$\binom{f(n)}{f(n-1)}$，可以得到

$$
\left(
\begin{matrix}
a & b \\
1 & 0
\end{matrix}
\right) \tag{2}^{n-1}*
\binom{f(1)}{f(0)}=\binom{f(n)}{f(n-1)}
$$

由此，我们只需要计算矩阵

$$
\left(
\begin{matrix}
a & b \\
1 & 0
\end{matrix}
\right)
$$

的n-1次方即可，对于这个矩阵的n-1次方，使用快速幂求出所求矩阵，便可以在$\log n$的时间内计算出f(n)的值。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int,int> pii;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rept(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define pb push_back
#define fi first
#define se second
#define mes(a,b) memset(a,b,sizeof a)
const int inf=0x3f3f3f3f;
const int mod=2013;
class matrix
{
    public:
        int arrcy[6][6];//arrcy为矩阵，下表从0开始
        int row,column;//row为矩阵的行，column为矩阵的列
        friend matrix operator *(matrix s1,matrix s2)
        {
            int i,j;
            matrix s3;
            for (i=0;i<s1.row;i++)
            {
                for (j=0;j<s2.column;j++)
                {
                    for (int k=0;k<s1.column;k++)
                    {
                        s3.arrcy[i][j]+=s1.arrcy[i][k]*s2.arrcy[k][j];
                        s3.arrcy[i][j]%=mod;
                    }
                }
            }
            s3.row=s1.row;
            s3.column=s2.column;
            return s3;
        }
};
matrix quick_pow(matrix s1,long long n)//矩阵快速幂函数，s1为矩阵，n为幂次
{
    matrix mul=s1,ans;
//将ans构造为单位矩阵
    ans.row=ans.column=s1.row;
    memset(ans.arrcy,0,sizeof ans.arrcy);
    for(int i=0;i<ans.row;i++)
        ans.arrcy[i][i]=1;
    while(n)
    {
        if(n&1) ans=ans*mul;
        mul=mul*mul;
        n/=2;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,a,b;
    cin>>n>>a>>b;
    matrix mul;
    mul.row=mul.column=2;
    mul.arrcy[0][0]=a;
    mul.arrcy[0][1]=b;
    mul.arrcy[1][0]=1;
    mul.arrcy[1][1]=0;
    matrix r;
    r.row=2;
    r.column=1;
    r.arrcy[0][0]=r.arrcy[1][0]=1;
    rep(i,0,n)
    {
        int x;
        cin>>x;
        if(!x)//当x=1时，x-1<0无法使用快速幂，答案为0，特判即可
        {
            cout<<1<<endl;
            continue;
        }
        matrix mm=quick_pow(mul,x-1);
        mm=mm*r;
        cout<<mm.arrcy[0][0]<<endl;
    }
    return 0;
}