hdu 4686 Arc of Dream (构造矩阵,快速幂)

hdu4686题目链接

题意:

An Arc of Dream is a curve defined by following function:


where
0 = A0
i = a i-1AX+AY
0 = B0
i = b i-1
BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

 

思路:

看n的1E18的范围也知道是矩阵快速幂。。

难点还是构造矩阵。

构造矩阵主要凭借经验,但是还是有一些规律可循:

  1. 对于求和的式子,如 s[n] = sum{F[1]..F[n]}类似的式子,我们只需要考虑如何构造F[n]即可。
  2. 尽量将要构造的表达式展开成,第n项,与前面项(第n-1项等)有关的形式。
  3. 观察2中展开的表达式的系数,每一个系数都亚奥出现在转移矩阵M中。
  4. 观察2中展开的表达式的项,基本每一项都要整体或者以其他形式出现在初始矩阵M1中
  5. 我们并不很关心初始项。
  6. 难点其实在于构造M1矩阵,也就是说哪些项是重要的。一般而言,可能有的项是,s[n],f[n],常数项,以及为了构造出f[n]的辅助项。

对于这道题:

 

然后矩阵快速幂即可。

1A

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz