题解

· · 题解

设 n 阶图形灌水面积为 a_n，n 阶图形旋转 90^\circ 的灌水面积为 b_n。

根据上图，则有

a_n=2a_{n-1}+2b_{n-1}+2^n-1+2^{n-1}-1 b_n=a_{n-1}+2b_{n-1}+2^{n-1}-1

两式相减，得

a_n-b_n=a_{n-1}+2^n-1

稍微变形，得

a_{n-1}-a_{n-2}-2^{n-1}+1=b_{n-1}

带回原式，得

a_n=4a_{n-1}-2a_{n-2}+2^{n-1}

稍微变形，得

a_n+2^n=4(a_{n-1}+2^{n-1})-2(a_{n-2}+2^{n-2})

设 f_n=a_n+2^n，则有

f_n=4f_{n-1}-2f_{n-2}

Sol 1：

根据二阶线性递推序列通项公式，有

f_n=(\frac32-\sqrt2)(2-\sqrt2)^{n-1}+(\frac32+\sqrt2)(2+\sqrt2)^{n-1}

则

a_n=(\frac32-\sqrt2)(2-\sqrt2)^{n-1}+(\frac32+\sqrt2)(2+\sqrt2)^{n-1}-2^n

利用 Cipolla 算法求出模意义下的 \sqrt2 即可。

Sol 2：

事实上，看到 f_n=4f_{n-1}-2f_{n-2}，你就可以利用判别式 p^2+4q 发现需要模意义下的 \sqrt2，而且，根据欧拉准则，2 是题目给定的模数的二次剩余。

所以，根据费马小定理和二阶线性递推序列通项公式的形式不难得到

f_n=f_{n\mod(p-1)}

矩阵快速幂即可。

对于一个二阶线性递推序列，若判别式是二次剩余，则可以直接使用扩展欧拉定理+矩阵快速幂。

若判别式不是二次剩余，则参考 P4000。