HDU 5895 Mathematician QSC（逆元应用+矩阵快速幂+数论知识）—

发布时间：2020-12-13 21:18:38 所属栏目：PHP教程来源：网络整理

导读：传送门 Mathematician QSC Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 208Accepted Submission(s): 101 Problem Description QSC dream of becoming a mathematician,he believes that every

传送门

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,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

题目大意：

首先定义了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) 等于甚么呢：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!