題意：A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2)；給定三個值N，X，Y求S(N):S(N) = A(0)2 +A(1)2+……+A(n)2。

思路：原來我們講的斐波那契數列是： F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2)

這道題規定了另一種斐波那契數列形式：A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2)

其實原理是一樣的！
我們以前快速求Fibonacci數列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1第n項的方法是！！？？！！
構造常系數矩陣！
（一）Fibonacci數列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.
解法：
考慮1×2的矩陣【f[n-2],f[n-1]】。根據fibonacci數列的遞推關系，我們希望通過乘以一個2×2的矩陣，得到矩陣【f[n-1],f[n]】=【f[n-1],f[n-1]+f[n-2]】
很容易構造出這個2×2矩陣A，即：
０ １
１ １
所以，有【f[1],f[2]】×A＝【f[2],f[3]】
又因為矩陣乘法滿足結合律，故有：
【f[1],f[2]】×A n-1=【f[n],f[n+1]】
這個矩陣的第一個元素即為所求。
至于如何快速求出A n-1，相信大家都會，即遞歸地：n為偶數時，An=(A n/2)2；n為奇數時，An=(A n/2)2*A。
問題（一）解決。
（二）數列f[n]=f[n-1]+f[n-2]+1,f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.
解法：
仿照前例，考慮1×3的矩陣【f[n-2],f[n-1],1】，希望求得某3×3的矩陣A，使得此1×3的矩陣乘以A得到矩陣：【f[n-1],f[n],1】＝【f[n-1],f[n-1]+f[n-2]+1,1】
容易構造出這個3×3的矩陣A，即：
０ １ ０
１ １ ０
０ １ １
問題（二）解決。
（三）數列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.
解法：
仿照前例，考慮1×4的矩陣【f[n-2],f[n-1],n,1】，希望求得某4×4的矩陣A，使得此1×4的矩陣乘以A得到矩陣：
【f[n-1],f[n],n+1,1】＝【f[n-1],f[n-1]+f[n-2]+n+1,n+1,1】
容易構造出這個4×4的矩陣A，即：
０ １ ０ ０
１ １ ０ ０
０ １ １ ０
０ １ １ １
問題（三）解決……
（四）數列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的前n項和s[n]的快速求法（不考慮高精度）.
解法：
雖然我們有S[n]=F[n+2]-1，但本文不考慮此方法，我們想要得到更一般的方法。
考慮（一）的矩陣A，容易發現我們要求【f[1],f[2]】×（A+A2+A3+…+AN-1）。很多人使用一種很數學的方法構造一個2r*2r（r是A的階數，這里為2）的矩陣來計算，這種方法比較麻煩且很慢，這里不再介紹。下面考慮一種新方法。
仿照之前的思路，考慮1×3的矩陣【f[n-2],f[n-1],s[n-2]】，我們希望通過乘以一個3×3的矩陣A，得到1×3的矩陣：
【f[n-1],f[n],s[n-1]】=【f[n-1],f[n-1]+f[n-2],s[n-2]+f[n-1]】
容易得到這個3×3的矩陣是：
０ １ ０
１ １ １
０ ０ １
然后…………容易發現，這種方法的矩陣規模是(r+1)*(r+1)，比之前流行的方法好得多。
（五）數列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的前n項和s[n]的快速求法（不考慮高精度）.
解法：
結合（三）（四），容易想到……
考慮1×5的矩陣【f[n-2],f[n-1],s[n-2],n,1】,
我們需要找到一個5×5的矩陣A，使得它乘以A得到如下1×5的矩陣：
【f[n-1],f[n],s[n-1],n+1,1】
=【f[n-1], f[n-1]+f[n-2]+n+1,s[n-2]+f[n-1],n+1,1】
容易構造出A為：
０ １ ０ ０ ０
１ １ １ ０ ０
０ ０ １ ０ ０
０ １ ０ １ ０
０ １ ０ １ １
然后……問題解決。
一般地，如果有f[n]=p*f[n-1]+q*f[n-2]+r*n+s
可以構造矩陣A為：
０ q 0 0 0
1 p 1 0 0
0 0 1 0 0
0 r 0 1 0
0 s 0 1 1
更一般的，對于f[n]=Sigma(a[n-i]*f[n-i])+Poly(n)，其中0<i<=某常數c, Poly (n)表示n的多項式，我們依然可以構造類似的矩陣A來解決問題。
設Degree(Poly(n))=d, 并規定Poly(n)=0時，d=-1，此時對應于常系數線性齊次遞推關系。則本方法求前n項和的復雜度為：
((c+1)+(d+1))3*logns

所以對于這道題，

我們可以根據(s[n-2], a[n-1]^2, a[n-1]*a[n-2], a[n-2]^2) * A = (s[n-1], a[n]^2, a[n]*a[n-1], a[n-1]^2)

能夠求出關系矩陣

? 　　 ?| ?1 ?0 ?0 ?0 ?? |?
A = ? ?| 1 x^2 1 ?x ? |
? 　　 ?| 0 ?y^2 ?0 0 ?|
? ? ? ? ?| 0 ?2*x*y 0 y |

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

?

View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <string> 5 #include <algorithm> 6 #include <iostream> 7 using namespace std; 8 const int N=5; 9 const int mod=10007; 10 11 typedef struct In{ 12 __int64 m[N][N]; 13 }Matrix; 14 Matrix init,unit,S; 15 __int64 n,x,y; 16 17 void Init(){ 18 for(int i=1;i<N;i++){ 19 for(int j=1;j<N;j++){ 20 if(i==1&&j==1) init.m[i][j]=1; 21 else if(i==2&&j==1) init.m[i][j]=1; 22 else if(i==2&&j==2) init.m[i][j]=x*x%mod; 23 else if(i==2&&j==3) init.m[i][j]=1; 24 else if(i==2&&j==4) init.m[i][j]=x%mod; 25 else if(i==3&&j==2) init.m[i][j]=y*y%mod; 26 else if(i==4&&j==2) init.m[i][j]=2*x*y%mod; 27 else if(i==4&&j==4) init.m[i][j]=y%mod; 28 else init.m[i][j]=0; 29 unit.m[i][j]=(i==j); 30 if(i==1) S.m[i][j]=1; 31 else S.m[i][j]=0; 32 } 33 } 34 } 35 36 Matrix Mul(Matrix a,Matrix b){ 37 Matrix c; 38 for(int i=1;i<N;i++) 39 for(int j=1;j<N;j++){ 40 c.m[i][j]=0; 41 for(int k=1;k<N;k++){ 42 c.m[i][j]+=a.m[i][k]*b.m[k][j]; 43 c.m[i][j]%=mod; 44 } 45 } 46 return c; 47 } 48 49 Matrix Pow(Matrix a,Matrix b){ 50 while(n){ 51 if(n&1) b=Mul(a,b); 52 a=Mul(a,a); 53 n>>=1; 54 } 55 return b; 56 } 57 58 void Debug(Matrix a){ 59 for(int i=1;i<N;i++){ 60 for(int j=1;j<N;j++) 61 printf("%d ",a.m[i][j]); 62 puts(""); 63 } 64 } 65 66 int main(){ 67 68 // freopen("data.in","r",stdin); 69 // freopen("data.out","w",stdout); 70 71 while(scanf("%I64d%I64d%I64d",&n,&x,&y)!=EOF){ 72 Init(); 73 Matrix x=Pow(init,unit); 74 x=Mul(S,x); 75 // Debug(x); 76 printf("%I64d\n",x.m[1][1]%mod); 77 } 78 return 0; 79 }

轉載于:https://www.cnblogs.com/Hug-Sea/articles/2479752.html

總結

以上是生活随笔為你收集整理的HDU 3306 Another kind of Fibonacci的全部內容，希望文章能夠幫你解決所遇到的問題。

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