bsgs – Tgotp-Blog

5104: Fib数列

首先发现递推是解决不了这个问题的.

考虑用通项公式解决.

有公式f_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n)

那么即求解:

$$ a \equiv \frac{1}{\sq[......]

Read more

4128: Matrix

简单观察即可发现用BSGS大力可做,然而算了算复杂度O(\sqrt p * n^3)炸掉了

此时用随机化的思想,生成一个1*n的矩阵,乘上原矩阵,即可少一个n,然后正常做即可.

c++代码如下: