传送门
Mathematician QSC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 208 Accepted Submission(s): 101
Problem Description
QSC dream of becoming a mathematician, he believes that everything in this world has a mathematical law.
Through unremitting efforts, one day he finally found the QSC sequence, it is a very magical sequence, can be calculated by a series of calculations to predict the results of a course of a semester of a student.
This sequence is such like that, first of all,f(0)=0,f(1)=1,f(n)=f(n−2)+2∗f(n−1)(n≥2)Then the definition of the QSC sequence is g(n)=∑ni=0f(i)2. If we know the birthday of the student is n, the year at the beginning of the semester is y, the course number x and the course total score s, then the forecast mark is xg(n∗y)%(s+1).
QSC sequence published caused a sensation, after a number of students to find out the results of the prediction is very accurate, the shortcoming is the complex calculation. As clever as you are, can you write a program to predict the mark?
Input
First line is an integer T(1≤T≤1000).
The next T lines were given n, y, x, s, respectively.
n、x is 8 bits decimal integer, for example, 00001234.
y is 4 bits decimal integer, for example, 1234.
n、x、y are not negetive.
1≤s≤100000000
Output
For each test case the output is only one integer number ans in a line.
Sample Input
2
20160830 2016 12345678 666
20101010 2014 03030303 333
Sample Output
题目大意：
首先定义了1个 f() 函数，f(n)=2∗f(n−1)+f(n−2),f(1)=1,f(0)=0， 然后又定义了1个 g() 函数 , g(n)=∑ni=0f(i)2,
最后让你求的是 xg(n∗y)%(s+1)， 其中 x,y,n,s 都是输入的。
解题思路：
这个题目其实不是很难，仔细分析1下还是挺简单的，首先我们1看到这个 f() 函数的表达式，1定会联想到矩阵快速幂，那末我们首先将 f(n)
能够通过矩阵快速幂得到，具体怎样得到的呢，我现在来讲1下：
首先，我们设1个矩阵 A ，这就是那个转移的矩阵，也就是说需要构造1个矩阵 A 使得 (f(n−2),f(n−1))∗A=(f(n−1),f(n)) 成立，那末现在 A
1定是1个 2∗2 的矩阵，然后在根据 f(n) 的递推式得到 A 矩阵中的具体值，算出来是：
0112
然后再来分析我们要求的式子： xg(n∗y)%(s+1)，如果满足 g(n∗y)≥Phi(s+1) 的时候我们可以将其转化为
xg(x∗y)%Phi(s+1)+Phi(s+1)%(s+1)——(1) ，否则只能暴力计算，然后我们发现只有当 n∗y≥11 的时候才暴力计算也很简单了，直接求，
然后快速幂就ok了，关键是解决上面 (1) 式的那个问题，首先我们看1下 g(n) 能不能写成关于 f() 的比较简单的式子，然后我们将其展开发现
与 f(i)∗f(i+1) 有关系，那末 f(i)∗f(i+1) 等于甚么呢：
f
