矩阵快速幂 – Tgotp-Blog

4128: Matrix

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

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

c++代码如下:

 

3329: Xorequ

打表发现对于2^x是个答案构成斐波那契数列

2^n直接 矩阵快速幂即可。

考虑n,通过打表也可以发现其实质就是数以二进制形式表示,没有任意相邻两位同为1,那么可把n分为多个x^n次方来搞,

如果有两位相邻,就跳过较小那位,搞定。

c++代码如下:
[crayon-5b50a[......]

Read more

1009: [HNOI2008]GT考试

神题,我自己反正感觉暂时不可能独立想出来。。。

好blog推荐http://blog.csdn.net/jeremygjy/article/details/50779475

c++代码如下:

 

&nb[......]

Read more

codevs 3773 fib

矩阵快速幂 + 动态开点 + 记忆化搜索。

c++代码如下:

 

T8017 小澳的坐标系

首先打表,f[1] = 3,f[2] = 7,f[3]=17,f[4] = 41;

得到规律f[i] = 2*f[i-1] + f[i-2];

然后手测数据发现只能跑 1e6;

然后直接套矩阵优化。

搞定。

还有一种打表的方法,发现能跑出1e6,那么我们每隔1e6打个表[......]

Read more

欧拉筛 & 矩阵乘法 & 矩阵快速幂