挺好的递推+矩阵快速幂题

题面:有一个m面的骰子,问投n次使投到第6面为偶数次的方案数

首先考虑递推，设f(i,j,k)为投i次的情况，j为0或1 (0为本次未投到第6面,1为投到了)，k为0或1 (当前投到第6面次数的奇和偶,0为偶,1为奇)

转移方程为$f(n,1,0) = f(n-1,1,1) + f(n-1,0,1)$

$f(n,1,1) = f(n-1,1,0) + f(n-1,0,0)$

$f(n,0,0) = m-1 * f(n-1,1,0) + m-1 * f(n-1,0,0)$

$f(n,0,1) = m-1 * f(n-1,1,1) + m-1 * f(n-1,0,1)$

看到n的范围$10^{18}$ wow，一眼dz，肯定要快速幂,根据递推可以想到矩阵快速幂，下面开始推转移矩阵

可以想到

$$\begin{bmatrix}f(n-1,1,0) & f(n-1,1,0) & f(n-1,0,0) & f(n-1,0,1) \\\end{bmatrix}$$

应该转移为

$$\begin{bmatrix}f(n,1,0) & f(n,1,0) & f(n,0,0) & f(n,0,1)\end{bmatrix}$$

所以根据递推转移方程考虑转移矩阵，则可建出矩阵为:

$$\begin{bmatrix}0 & 1 & m-1 & 0\\1 & 0 & 0 & m-1\\0 & 1 & m-1 & 0\\1 & 0 & 0 & m-1\\\end{bmatrix}$$

初始矩阵为$f(1)$ 即 $\begin{bmatrix}0 , 1 , m-1 , 0\end{bmatrix}$

OO最后直接跑矩阵快速幂就行了OO

复杂度为$O(4^3*log(n))$

好像这道题还有数学方法,但不会