佳佳的 Fibonacci

佚名 6年前 (2019-05-04) 随笔 497人围观抢沙发百度已收录

Description

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Analysis

10分：暴力+把m和n输反，你将获得10分的好成绩(Just like me.)

70分：暴力+把m和n输对，你将获得70分的好成绩

100分：矩阵加速

设

$ T(n)=1F_1+2F_2+3F_3+......+nF_n $

$S(n)=F_1+F_2+F_3+......+F_n$

则有：

$n*S(n)-T(n)=(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

移项可得

$T(n)=n*S(n)-(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

客官且慢，观察可以发现

$(n-1)*F_1+(n-2)*F_2+(n-3)*F_3+......+1*F_{n-1}$

不就是S(1)~S(n-1)的前缀和么

所以再设

$G(n)=G(n-1)+S(n)$

但一项一项来太慢了

用矩阵加速吧

于是设矩阵

$[F(n-1),F(n),S(n),G(n)]$

转移矩阵自然出来了

$[0,1,1,1]$

$[1,1,1,1]$

$[0,0,1,1]$

$[0,0,0,1]$

差一点就成阶梯矩阵了呢

So：

70：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,mod,now,ans=3,a=1,b=1;
int main(){
    cin>>n>>mod;
    if(n==1){cout<<1%mod;return 0;}
    if(n==2){cout<<3%mod;return 0;}
    for(register int i=3;i<=n;++i){
        now=(a+b)%mod;
        a=b,b=now,ans=(ans+i%mod*now%mod)%mod;
    }
    cout<<ans;
    return 0;
}

100：

#include<cstdio>
#include<cstring>
#define re register
#define in inline
#define int long long
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=-1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return b?-s:s;
}
int n,m;
struct mat{
    int v[5][5];
    mat operator*(const mat &t)const
        {
            mat c;
            memset(c.v,0,sizeof(c.v));
            for(re int i=1;i<=4;++i)
                for(re int j=1;j<=4;++j)
                    for(re int k=1;k<=4;++k)
                        c.v[i][j]=(c.v[i][j]+v[i][k]*t.v[k][j]%m)%m;
            return c;
        }
}I,S,T;
in mat ksm(mat ba,int k)
{
    mat ans=I;
    while(k)
    {
        if(k&1) ans=ans*ba;
        k>>=1;
        ba=ba*ba;
    }
    return ans;
}
signed main()
{
    n=read(),m=read();
    I.v[1][1]=I.v[2][2]=I.v[3][3]=I.v[4][4]=1;
    S.v[1][1]=S.v[1][2]=S.v[1][3]=S.v[1][4]=1;
    T.v[1][1]=T.v[2][1]=T.v[2][2]=T.v[3][1]=T.v[3][2]=T.v[3][3]=T.v[3][4]=T.v[4][3]=1;
    if(n==1){
        printf("%lld\n",1ll%m);
        return 0;
    }
    S=S*ksm(T,n-2);
    int pn1=S.v[1][1];
    S=S*T;
    printf("%lld\n",(n%m*S.v[1][2]%m-pn1+m)%m);
    return 0;
}