傳送門(mén)
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個(gè) f() 函數(shù)，f(n)=2?f(n?1)+f(n?2),f(1)=1,f(0)=0， 然后又定義了1個(gè) g() 函數(shù) , g(n)=∑ni=0f(i)2,
最后讓你求的是 xg(n?y)%(s+1)， 其中 x,y,n,s 都是輸入的。
解題思路：
這個(gè)題目其實(shí)不是很難，仔細(xì)分析1下還是挺簡(jiǎn)單的，首先我們1看到這個(gè) f() 函數(shù)的表達(dá)式，1定會(huì)聯(lián)想到矩陣快速冪，那末我們首先將 f(n)
能夠通過(guò)矩陣快速冪得到，具體怎樣得到的呢，我現(xiàn)在來(lái)講1下：
首先，我們?cè)O(shè)1個(gè)矩陣 A ，這就是那個(gè)轉(zhuǎn)移的矩陣，也就是說(shuō)需要構(gòu)造1個(gè)矩陣 A 使得 (f(n?2),f(n?1))?A=(f(n?1),f(n)) 成立，那末現(xiàn)在 A
1定是1個(gè) 2?2 的矩陣，然后在根據(jù) f(n) 的遞推式得到 A 矩陣中的具體值，算出來(lái)是：
0112
然后再來(lái)分析我們要求的式子： xg(n?y)%(s+1)，如果滿(mǎn)足 g(n?y)≥Phi(s+1) 的時(shí)候我們可以將其轉(zhuǎn)化為
xg(x?y)%Phi(s+1)+Phi(s+1)%(s+1)——(1) ，否則只能暴力計(jì)算，然后我們發(fā)現(xiàn)只有當(dāng) n?y≥11 的時(shí)候才暴力計(jì)算也很簡(jiǎn)單了，直接求，
然后快速冪就ok了，關(guān)鍵是解決上面 (1) 式的那個(gè)問(wèn)題，首先我們看1下 g(n) 能不能寫(xiě)成關(guān)于 f() 的比較簡(jiǎn)單的式子，然后我們將其展開(kāi)發(fā)現(xiàn)
與 f(i)?f(i+1) 有關(guān)系，那末 f(i)?f(i+1) 等于甚么呢：
f
