斐波那契数列卷积

题目链接:

斐波那契数列卷积


示例1
输入

3

输出

2

示例2
输入

19260817

输出

511682927

解题思路

提前我们要知道 Fn=Fn-1+Fn-2
规律是适合的,因为写起来太麻烦所以这就举个例子说明吧,
A7= F0* F7 + F1* F6 + F2* F5 + F3* F4 + F4* F3 + F5* F2 + F6* F1 + F7* F0
A6= F0* F6 + F1* F5 + F2* F4 + F3* F3 + F4* F2 + F5* F1 + F6* F0
A7-A6=F0(F7-F6) + F1(F6-F5) + F2(F5-F4) + F3(F4-F3) + F4(F3-F2) + F5(F2-F1) + F6(F1-F0) + F7 F0
因为 F1=1,F0=0;所以F6(F1-F0)=F6;
A7-A6=F0
F5 + F1* F4 + F2* F3 + F3* F2 + F4* F1 + F5* F0 + F6
A7-A6=A5+F6;
也就是 An=An-1+An-2+Fn-1
这样就可以用矩阵快速幂来构造一个矩阵来求了(感谢bly提供的方程,tql)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;

struct node{
    ll a[4][4];
};

node mul(node a,node b)
{
    node ans;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            ans.a[i][j]=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<4;k++)
            {
                ans.a[i][j]=(ans.a[i][j]+((a.a[i][k]%mod)*(b.a[k][j]%mod))%mod)%mod;
            }
        }
    }
    return ans;
}

node poww(node a,ll b)
{
    node ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=0;i<4;i++)    ans.a[i][i]=1;
    while(b)
    {
        if(b&1)    ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}

node yl,bly;

int main()
{
    ios::sync_with_stdio(0);
    ll n;
    cin>>n;
    memset(yl.a,0,sizeof(yl.a));
    memset(bly.a,0,sizeof(bly.a));
    yl.a[0][0]=1;
    yl.a[0][1]=1;
    yl.a[0][2]=1;
    yl.a[1][0]=1;    
    yl.a[2][2]=1;
    yl.a[2][3]=1;
    yl.a[3][2]=1;
    bly.a[2][0]=1;
    bly.a[0][0]=1;
    bly.a[3][0]=1;
    if(n==1)    cout<<0<<endl;
    else if(n==2)    cout<<1<<endl;
    else
    {
        node ans=poww(yl,n-2);
        ans=mul(ans,bly);
        cout<<ans.a[0][0]<<endl;
    }
    return 0;
}

  目录