一道遞推題目 ?

得到遞推關(guān)系為 ?f[n]=f[n-1]+f[n-3]+f[n-4];?

用普通的枚舉算法會超時

所以要用矩陣快速冪來加速

轉(zhuǎn)化為矩陣即為： ?

+
1 0 1 1 ? ? ? F(N-1)　　F(N) ? ? ??
1 0 0 0 ?* ? ?F(N-2) ?= ? F(N-1) ??
0 1 0 0 ? ? ? F(N-3)　　F(N-2)
0 0 1 0 ? ? ? F(N-4)　　F(N-3)

? ?

1 0 1 1（n-4） ? ? ? F(4)　　F(N) ? ? ??
1 0 0 0 ? ? ? ? ? ?* ? ? ?F(3) ?= ? F(N-1) ??
0 1 0 0 ? ? ? ? ? ? ? ? ? F(2)　　F(N-2)
0 0 1 0 ? ? ? ? ? ? ? ? ? F(1)　　F(N-3)

?

?

所以f（n） 為 矩陣的n-4次冪 ?的第一行 與已知的相乘 ? ?（n-4 為 ?n-3-1即可 ? 這是差值 再加一為個數(shù)）

#include<iostream> #include<cstdio> #include<cstring>using namespace std;int n,k;int q[5]={0,2,4,6,9}; struct matrix{int arr[4][4]; };matrix multi( matrix a,matrix b ) {matrix c;for(int i=0;i<4;i++)for(int j=0;j<4;j++){c.arr[i][j]=0;for(int w=0;w<4;w++)c.arr[i][j]=(c.arr[i][j]+a.arr[i][w]*b.arr[w][j]%k)%k;}return c; }int fast(matrix a,int x){matrix ans;memset(ans.arr,0,sizeof(ans.arr));for(int i=0;i<4;i++)ans.arr[i][i]=1;while(x){if(x&1){ans=multi(ans,a);}x>>=1;a=multi(a,a);}int sum=0;for(int i=0;i<4;i++){sum+=ans.arr[0][i]*q[4-i];sum%=k;}return sum; }int main(){while(scanf("%d%d",&n,&k)==2){if(n<=4){printf("%d\n",q[n]%k);continue;}else{matrix a={1,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0};printf("%d\n",fast(a,n-4)%k);}}return 0; } View Code

矩陣還是用結(jié)構(gòu)體寫方便。

?

轉(zhuǎn)載于:https://www.cnblogs.com/bxd123/p/10347814.html

總結(jié)

以上是生活随笔為你收集整理的Queuing HDU2604的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。