看到这题就觉得是矩阵快速幂,但是g(n)里面还有g(n)不好处理。其实应该想到,既然有取余,就一定有循环节。再做的时候想到会有循环节了,但想到是对1e9+7取余,则循环节最大就可能是10^18,再加上爆了10^7范围内的数据没发现循环节,就没想了。看来有时候不是题目做不出来,而是没有往下面想的勇气
既然对1e9+7取余有循环节,假设是k1,则我们就有g(n)%1000000007=g(n%k1)%1000000007,则就要求g(g(g(n)))就相当于求g(g(g(n))%k1),而求g(g(n))%k1,同理,可爆出g(n)对k1取余的循环节k2,则题目就暂时变成了求g(g(g(n%k2))%k1),然后就可以用矩阵快速幂求解(程序爆出k1=222222224,k2=183120)
1 |
|