【bzoj4002】[JLOI2015]有意义的字符串

2015年4月23日2,5611

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带入求出通项

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

 

  • De℃,.: )2015年4月24日 上午11:53 回复

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

    #1