Another kind of Fibonacci （矩陣連乘）

Another kind of Fibonacci 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 <= 2^31 – 1 X : 2<= X <= 2^31– 1 Y : 2<= Y <= 2^31 – 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 題解： AC代碼： #include<iostream> #include<memory.h> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<iomanip> #include<vector> #include<list> #include<map> #include<algorithm> typedef long long LL; const LL maxn=1000+10; const LL mod=10000000; using namespace std; const int N=4; const int MOD=10007; struct Matrix { LL m[N][N]; }; Matrix I= {1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1}; Matrix multi(Matrix a,Matrix b) { Matrix c; for(int i=0;i<N;i++) for(int j=0;j<N;j++) { c.m[i][j]=0; for(int k=0;k<N;k++) { c.m[i][j]+=a.m[i][k]*b.m[k][j]%MOD; } c.m[i][j]%=MOD; } return c; } Matrix quick_mod(Matrix a,LL k) { Matrix ans=I; while(k!=0) { if(k&1) { ans=multi(ans,a); } k>>=1; a=multi(a,a); } return ans; } int main() { LL x,y,z; while(~scanf("%lld%lld%lld",&z,&x,&y)) { Matrix A={ 1, (x%MOD*x%MOD)%MOD, (y%MOD*y%MOD)%MOD, (2*x%MOD*y%MOD)%MOD, 0, (x%MOD*x%MOD)%MOD, (y%MOD*y%MOD)%MOD, (2*x%MOD*y%MOD)%MOD, 0, 1, 0, 0, 0, x%MOD, 0, y%MOD }; Matrix ans=quick_mod(A,z-1); LL t=(ans.m[0][0]%MOD*2+ans.m[0][1]%MOD+ans.m[0][2]%MOD+ans.m[0][3]%MOD)%MOD; printf("%lld\n",t); } return 0; }