傳送門
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
