題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2855

題目意思：求一個式子g[n]=∑C(n,k)*f[k]，n很大，很明顯是一個矩陣快速冪。可以打表發現g[n]=f[2*n]劃開可以發現g[n]=3*g[n-1]-f[n-2]。

思路：我們現在可以證明一下

f[2*n]=f[2*n-1]+f[2*n-2];

其中f[2*n-1]=f[2*n-2]+f[2*n-3]

f[2*n-2]=f[2*n-3]+f[2*n-4]

所以f[2*n]=f[2*n-2]+f[2*n-3]+f[2*n-3]+f[2*n-4]=2*f[2*n-2]+f[2*n-3]=2*f[2*n-2]+f[2*n-3]+f[2*n-4]-f[2*n-4]=3*f[2*n-2]-f[2*n-4]。我們化簡一下g[n]=3*g[n-1]-g[n-2]。我們可以通過打表得到這個結論。

現在我們可以從數學上證明一下這個結論。

方法：1.通項公式：f[n]=(1/sqrt(5))*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)??

　　　2.二項式：(1+a)^n=∑(C(n,k)*a^k)(0<=k<=n)

∑C(n,k)*f[k]=(1/sqrt(5))*∑C(n,k)*(((1+sqrt(5))/2)^k-((1-sqrt(5))/2)^k)

　　　　　=(1/sqrt(5))*(∑C(n,k)*((1+sqrt(5))/2)^k-∑C(n,k)*((1-sqrt(5))/2)^k)?

　　　　　=(1/sqrt(5))*((3+sqrt(5))/2)^n-((3-sqrt(5))/2)^n)?

　　　　　=(1/sqrt(5))*((1+sqrt(5))/2)^(2*n)-((1-sqrt(5))/2)^(2*n))

　　　　　=f[2*n]?

這個組合數的應用感覺十分有意思。

代碼：

//Author: xiaowuga #include<bits/stdc++.h> #define maxx INT_MAX #define minn INT_MIN #define inf 0x3f3f3f3f #define N 2 using namespace std; long long MOD; typedef long long ll; ll n,size=2;//第n項，矩陣大小 struct Matrix{ll mat[N][N];void clear(){memset(mat,0,sizeof(mat));}Matrix operator * (const Matrix & m) const{Matrix tmp;int i ,j,k;tmp.clear();for( i=0;i<size;i++)for( k=0;k<size;k++){if(mat[i][k]==0) continue;for( j=0;j<size;j++){tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;tmp.mat[i][j]%=MOD;}}return tmp;} }; Matrix POW(Matrix m,ll k){Matrix ans;memset(ans.mat,0,sizeof(ans.mat));for(int i=0;i<size;i++) ans.mat[i][i]=1;while(k){if(k&1) ans=ans*m;k/=2;m=m*m;}return ans; } int main() {Matrix m;m.clear();m.mat[0][0]=3;m.mat[0][1]=-1;m.mat[1][0]=1;m.mat[1][1]=0;int T;cin>>T;for(int i=0;i<T;i++){cin>>n>>MOD;if(n==0) {cout<<0<<endl;continue;}Matrix ans=POW(m,n-1);ll sum=(ans.mat[0][0]%MOD+MOD)%MOD;cout<<sum<<endl;} return 0; } View Code

?

?

轉載于:https://www.cnblogs.com/xiaowuga/p/7352261.html

總結

以上是生活随笔為你收集整理的HDU2855—Fibonacci Check-up的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。