11.5 NOIP 模擬賽 T1. 榮耀
思路
\(f(n)\): \(n\) 個位置中 \(0\) 號勛章出現偶數次的方案數
\(g(n)\): \(n\) 個位置中 \(0\) 號勛章出現奇數次的方案數
\[f(n) = m \cdot f(n-1) + g(n-1) \\
g(n) = f(n-1) + m \cdot g(n-1)
\]
可以
\[\begin{bmatrix}
f(n) \\
g(n)
\end{bmatrix}
= A^{n-1} \times
\begin{bmatrix}
f(1) \\
g(1)
\end{bmatrix}
= A^{n-1} \times
\begin{bmatrix}
m \\
1
\end{bmatrix}
\]
總結
太牛了狗狗
直接處理形態, 不要欽定選數
浙公網安備 33010602011771號