HDU 5895 Mathematician QSC(逆元应用+矩阵快速幂+数论知识)——2016 ACM/ICPC Asia Regional Shenyang Online

传送门

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(n2)+2f(n1)(n2)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(ny)%(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

题目大意:

首先定义了1个 f() 函数,f(n)=2f(n1)+f(n2),f(1)=1,f(0)=0, 然后又定义了1个 g() 函数 , g(n)=ni=0f(i)2,

最后让你求的是 xg(ny)%(s+1), 其中 x,y,n,s 都是输入的。

解题思路:
这个题目其实不是很难,仔细分析1下还是挺简单的,首先我们1看到这个 f() 函数的表达式,1定会联想到矩阵快速幂,那末我们首先将 f(n)

能够通过矩阵快速幂得到,具体怎样得到的呢,我现在来讲1下:

首先,我们设1个矩阵 A ,这就是那个转移的矩阵,也就是说需要构造1个矩阵 A 使得 (f(n2),f(n1))A=(f(n1),f(n)) 成立,那末现在 A

1定是1个 22 的矩阵,然后在根据 f(n) 的递推式得到 A 矩阵中的具体值,算出来是:
0112

然后再来分析我们要求的式子: xg(ny)%(s+1),如果满足 g(ny)Phi(s+1) 的时候我们可以将其转化为

xg(xy)%Phi(s+1)+Phi(s+1)%(s+1)(1) ,否则只能暴力计算,然后我们发现只有当 ny11 的时候才暴力计算也很简单了,直接求,

然后快速幂就ok了,关键是解决上面 (1) 式的那个问题,首先我们看1下 g(n) 能不能写成关于 f() 的比较简单的式子,然后我们将其展开发现

f(i)f(i+1) 有关系,那末 f(i)f(i+1) 等于甚么呢:

f

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU 5895 Mathematician QSC(逆元应用+矩阵快速幂+数论知识)——2016 ACM/ICPC Asia Regional Shenyang Online

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡