循环节 + 矩阵快速幂 - HDU 4291 A Short problem

时间:2024-10-16 20:06:20

A Short problem

Problem's Link


Mean:

给定一个n,求:g(g(g(n))) % 1000000007

其中:g(n) = 3g(n - 1) + g(n - 2),g(1) = 1,g(0) = 0

analyse:

很经典的题。
由于n特别大,直接求肯定不行。由于所有的模运算都会出现循环节,可以求出循环节。

由于模数是固定的,可以在本地暴力求出循环节。

对于1000000007,求得循环节为222222224;

对于222222224,求得循环节183120;

最内层对183120取模,将值传给第二层;第二层对222222224取模,将值传给最外层;最外层对1000000007。

这样就大大降低了时间复杂度。

根据递推式构造矩阵,使用矩阵快速幂来求a[n].

Time complexity: O(N)

view code