乍一看觉得需要矩阵快速幂,但是还有区间询问的问题,所以需要用线段树+矩阵乘法。
对于任意的长度大于2的区间长度[L,R]的询问,有如下:
其中:
因此我们只需要用线段树维护区间内M(L+2)到M(R)的乘积,注意矩阵乘法的方向顺序。
因为query函数的问题,段错误N次. 还有注意数组的大小,太大也会段错误。
1 | #include <cstdio> |
云腾致雨,露结为霜
乍一看觉得需要矩阵快速幂,但是还有区间询问的问题,所以需要用线段树+矩阵乘法。
对于任意的长度大于2的区间长度[L,R]的询问,有如下:
其中:
因此我们只需要用线段树维护区间内M(L+2)到M(R)的乘积,注意矩阵乘法的方向顺序。
因为query函数的问题,段错误N次. 还有注意数组的大小,太大也会段错误。
1 | #include <cstdio> |