斐波那契数列卷积

Link: 牛客挑战赛32-C

Description:

Problem solving:
这道题题意没啥好说的。看公式就能看懂。
这道题第一眼就觉得是矩阵快速幂的题。但是一直没找到通项公式。后来在bly的帮助下知道了通项公式：
a[n]=a[n-1]+a[n-2]+f[n-1]
然后直接矩阵快速幂就行了。

推理过程：

a[n]=f[1]*f[n-1]+f[2]*f[n-2]+f[3]*f[n-3]+f[4]*f[n-4]+...+f[n-2]*f[2]+f[n-1]*f[1]
a[n-1]=f[1]*f[n-2]+f[2]*f[n-3]+f[3]*f[n-4]+f[4]*f[n-5]+...+f[n-3]*f[2]+f[n-2]*f[1]

a[n]-a[n-1]=f[1]*f[n-3]+f[2]*f[n-4]+f[3]*f[n-5]+f[4]*f[n-6]+...+f[n-2]*f[1]+f[n-1]*f[1]
　　　　　　=a[n-2]+f[n-1]

即 a[n]=a[n-1]+a[n-2]+f[n-1]

如果推理过程觉得太抽象可以代几个数试试

矩阵快速幂的时候构建的两个矩阵如图

Code:

#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;
}