斐波那契数列卷积
- 2020 年 4 月 9 日
- 筆記
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; }
