Recursivesequence（HDU5950矩阵快速幂）

题目：

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, andi4i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Input：

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, andi4i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Output：

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

Hint：

In the first case, the third number is 85 = 2*1+2+3^4.
In the second case, the third number is 93 = 2*1+1*10+3^4 and the fourth number is 369 = 2 * 10 + 93 + 4^4.

题意：

奶牛报数，先给两个数a和b，分别是f[n-2],f[n-1]，之后每头奶牛i报数为f[i-1] + 2 * f[i-2] + i^4;给出n，求din头奶牛要报的数字，对2147493647取余。

思路：

看到这个式子知道这是一个矩阵快速幂，然后开始推式子，在我给队友写出平方差公式来队友看到杨辉三角形式后后，就去推7*7的矩阵快速幂了，但因为刚刚学这个，但结束就挂死在这个题上了。

具体式子如下：

之后就是套裸的矩阵快速幂就好了，个人感觉做题补题真的是长知识最快的方法啊。补题的时候自己直接用矩阵来写麻烦的要死，就把矩阵放在一个结构体中，顺便方便很多。

代码：

#include #include #include #include #include #include 

View Code