点击此处即可传送hdu 3306
**Another kind of Fibonacci**Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2005 Accepted Submission(s): 787Problem DescriptionAs 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.InputThere are several test cases.Each test case will contain three integers , N, X , Y .N : 2<= N <= 231 – 1X : 2<= X <= 231– 1Y : 2<= Y <= 231 – 1OutputFor 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 Sample Output6196
题目大意：就是给你三个数 n 和x,y， f(n) = x*f(n-1) + y*f(n-2); 然后求s(n) = f(0)^2 + f(1)^2 +….+f(n)^2，就是这样了; 解题思路：还是矩阵乘法取余； 直接上代码：
/*2015 – 8 – 14 下午Author: ITAK今天非常非常的不顺心啊。。。。今日的我要超越昨日的我，，明日的我要胜过今日的我，以创作出更好的代码为目标，不断地超越自己。*/;const int maxn = 4;const int mod = 10007;LL;typedef struct{LL m[maxn][maxn];}Matrix;Matrix P = {1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0};Matrix I = {1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1};Matrix matrix_mul(Matrix a, Matrix b){int i, j, k;Matrix c;for(i=0; i<maxn; i++){for(j=0; j<maxn; j++){c.m[i][j] = 0;for(k=0; k<maxn; k++)c.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod;c.m[i][j] %= mod;}}return c;}Matrix quick_mod(LL m){Matrix ans = I, b = P;while(m){if(m & 1)ans = matrix_mul(ans, b);m >>= 1;b = matrix_mul(b, b);}return ans;}int main(){LL n, x, y;while(~scanf(“%lld%lld%lld”,&n,&x,&y)){Matrix tmp;x %= mod;y %= mod;P.m[1][1] = (x*x) % mod;P.m[1][2] = (2*x*y) % mod;P.m[1][3] = (y*y) % mod;P.m[2][1] = x;P.m[2][2] = y;tmp = quick_mod(n);LL ans = (tmp.m[0][0]+tmp.m[0][1]+tmp.m[0][2]+tmp.m[0][3])%mod;cout<<ans<<endl;}return 0;}
一直觉得人应该去旅行，在年轻的时候，
