首页 > 代码库 > hdu 3306 Another kind of Fibonacci
hdu 3306 Another kind of Fibonacci
Another kind of Fibonacci
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1526 Accepted Submission(s): 583
Problem Description
As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)2 +A(1)2+……+A(n)2.
Input
There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 1
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 1
Output
For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
Sample Input
2 1 1 3 2 3
Sample Output
6 196
Author
wyb
Source
HDOJ Monthly Contest – 2010.02.06
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int mod=10007; struct mat { __int64 t[4][4]; void set() { memset(t,0,sizeof(t)); } } a,b; mat multiple(mat a,mat b,__int64 n,int p) { int i,j,k; mat temp; temp.set(); for(i=0; i<n; i++) for(j=0; j<n; j++) { if(a.t[i][j]!=0) for(k=0; k<n; k++) temp.t[i][k]=(temp.t[i][k]+a.t[i][j]*b.t[j][k])%p; } return temp; } mat quick_mod(mat b,__int64 n,__int64 m,int p) { mat t; t.set(); for(int i=0;i<n;i++) t.t[i][i]=1; while(m) { if(m&1) { t=multiple(t,b,n,p); } m>>=1; b=multiple(b,b,n,p); } return t; } void init(__int64 x,__int64 y) { b.set(); b.t[0][0]=1; b.t[1][0]=x*x%mod;b.t[1][1]=x*x%mod;b.t[1][2]=x;b.t[1][3]=1; b.t[2][0]=2*x*y%mod;b.t[2][1]=2*x*y%mod;b.t[2][2]=y; b.t[3][0]=y*y%mod;b.t[3][1]=y*y%mod; } int main() { __int64 n,x,y; while(cin>>n>>x>>y) { x=x%mod; y=y%mod; init(x,y); a=quick_mod(b,4,n-1,mod); cout<<(2*a.t[0][0]+a.t[1][0]+a.t[2][0]+a.t[3][0])%mod<<endl; } return 0; } /* A为特殊斐波那契额数列:A[0]=1,A[1]=1,A[n]=x*A[n-1]+y*A[n-2]; S[n]=∑A[i]^2=A[0]^2+A[1]^2+……+A[n]^2=S[n-1]+A[n]^2; =S[n-1]+x^2*A[n-1]^2+2*x*y*A[n-1]*A[n-2]+y^2*A[n-2]^2; 这样我们就能构造出一个4*4的初始矩阵和一个转换矩阵 初始矩阵B=|S[2] A[1]^2 A[1]*A[0] A[0]^2| 转换一次后结果T=|S[3] A[2]^2 A[2]*A[1] A[1]^2| 其中S[3]=S[2]+x*x*A[1]^2+2*x*y*A[1]*A[0]+y*y*A[0]^2; A[2]^2=x*x*A[1]^2+2*x*y*A[1]*A[0]+y*y*A[0]^2; A[2]*A[1]=x*A[1]^2+y*A[1]*A[0]; 转换矩阵Z= |1 0 0 0| |x^2 x^2 x 1| |2xy 2xy y 0| |y^2 y^2 0 0| 矩阵快速幂就可以了。 *转载请注明出处,谢谢。 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。