[原创]HDU 5895&&2016 ACM/ICPC Asia Regional Shenyang Online1004 Mathematician QSC [矩阵加速+欧拉降幂]【数论】

2016-09-19 20:02:35 Tabris_ 阅读数：454

https://blog.csdn.net/qq_33184171/article/details/52588817

------------------------.
Mathematician QSC

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 222 Accepted Submission(s): 109

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 x^g(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
317

Source
2016 ACM/ICPC Asia Regional Shenyang Online

------------------------.

f(0)=0,f(1)=1,f(n)=f(n−2)+2∗f(n−1)(n≥2) （f[n]^2,f[n+1]^2,f[n]*f[n+1],g[n]）
↑这是左矩阵
[0,1,0,0]
[1,4,2,1]
[0,4,1,0]
[0,0,0,1] ←这是右矩阵 //

/
/

--------------------------------------.