「BZOJ4002」[JLOI2015] 有意义的字符串

2015年4月23日3,0781

Description

 B 君有两个好朋友,他们叫宁宁和冉冉。

有一天,冉冉遇到了一个有趣的题目:输入 b;d;n,求((b+sqrt(D)/2)^N的整数部分,请输出结果 Mod 7528443412579576937 之后的结果吧。

Input

一行三个整数 b;d;n

Output

 一行一个数表示模 7528443412579576937 之后的结果。

Sample Input

1 5 9

Sample Output

76

HINT

 0 <b^2 < d< (b +1)2 < 10^18。

题解

http://blog.csdn.net/popoqqq/article/details/45148309

为什么我不知道高中课本有特征方程。。

\(a_{n+2}=p*a_{n+1}+q*a_n\)

的特征方程 \(x^2=px+q\)

得出方程的两个根x1,x2

如果两根不等

\(a_n=Ax_1^n+Bx_2^n\)

n=0,1带入求出通项

知道这个以后通项倒回去就简单了

 

说点什么

提醒
avatar
De℃,.: )
De℃,.: )

考的时候跪烂了矩阵还是挂掉了……