斐波那契數列卷積

Link: 牛客挑戰賽32-C

斐波那契數列卷積

Description:

輸入 3 輸出 2 示例2 輸入 19260817 輸出 511682927

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