按照题目提示,构造矩阵,用矩阵快速幂求解

构造矩阵:

大家一定做过这种题:求斐波那契数列第N项%1e9+7(N<=1e18)
单纯从数学上讲,我们可以使用矩阵快速幂解决。由于斐波那契数列的递推公式非常简单,所以可以很方便的构造矩阵。
$f[i]=f[i-1]+f[i-2]$
$$
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} \times
\begin{bmatrix}
f[i-1] \\
f[i-2]
\end{bmatrix} =
\begin{bmatrix}
f[i] \\
f[i-1]
\end{bmatrix}
$$

但是这个方程的参数是“恒定”的,也就是说,每一个f[i]都可以用f[i-1]和f[i-2]的“恒定”的“线性"组合得出(即单纯的相加)。
因此可以想象,$f[i]=a\times f[i-1]+b\times f[ i-2 ] (a,b为定值)$这样的方程的转移矩阵也非常简单。
考虑更加特殊的方程:$f[i]=i^2$
显然这个是可以用矩阵快速幂优化为O(logn)求的(因为你完全可以O(1)求,我们让它O(logn)求它若不肯岂不太不给面子了)
具体的转移矩阵是:
$$
\begin{bmatrix}
(i-1)^2\\
(i-1)\\
1
\end{bmatrix} \times
\begin{bmatrix}
1 & 0 & 1\\
2 & 1 & 1\\
0 & 0 & 1
\end{bmatrix} =
\begin{bmatrix}
i^2\\
i\\
1
\end{bmatrix}
$$
这样,我们就可以很容易地写出这道题的转移矩阵:
$$
\begin{bmatrix}
\begin{smallmatrix}
p & 1 & 1 & q & 0 & 0 & 0 & 0 & t & 0 & r & 1\\
1 & u & 1 & 0 & v & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & x & 0 & 0 & y & 0 & 1 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & z & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & -3\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{smallmatrix}
\end{bmatrix}\times
\begin{bmatrix}
\begin{smallmatrix}
a[i-1]\\
b[i-1]\\
c[i-1]\\
a[i-2]\\
b[i-2]\\
c[i-2]\\
w^{i-2}\\
z^{i-2}\\
i-2\\
i\\
(i-2)^2\\
1
\end{smallmatrix}
\end{bmatrix}=
\begin{bmatrix}
\begin{smallmatrix}
a[i]\\
b[i]\\
c[i]\\
a[i-1]\\
b[i-1]\\
c[i-1]\\
w^{i-1}\\
z^{i-1}\\
i-1\\
i+1\\
(i-1)^2\\
1
\end{smallmatrix}
\end{bmatrix}
$$
但是注意一点,能用矩阵快速幂优化的转移矩阵,必须是如上的参数为恒值的。
比如$f[x]=f[x-1]+x\times f[x-2]$貌似就不能用矩阵快速幂优化(至少我不会)

代码实现:

注意到乘法时会出现超出long long 范围的情况,因此我们可以使用一种黑科技:O(1)快速乘
将long long 强制转化为double,在误差的情况下进行乘法即可。

这样,总的时间复杂度依旧是o(nlogn)