CF60E Mushroom Gnomes
10月10日的茶
考虑蘑菇在一分钟后有什么变化
\[\begin{align}
&S_0 = a_1 + a_2 + a_3 + a_4 ... + a_{n-1} + a_{n} \\
&S_1 = a_1 +(a_1 + a_2) + a_2 + (a_2 + a_3) + a_3 + ... + a_{n-1} + (a_{n-1} + a_{n}) + a_{n}\\
&S_1 = S_0 + a_1 + a_2 + a_2 + a_3 + a_3 + ... + a_{n-1} + a_{n-1} + a_{n} \\
&S_1 = S_0 + 2S_0 - (a_1 + a_n) \\
&S_1 = 3S_0 - (a_1 + a_n)
\end{align}
\]
设\(C = -(a_1 + a_n)\) 可见可用矩阵描述转移
\[\begin{bmatrix}
S_1\\
C
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
S_0\\
C
\end{bmatrix}
\]
第二次生长前还要进行一次排序，排序后 \(a_1\) 作为最小值不变，而最大值不再是 \(a_n\)
按照上面的变化，可以看出第一分钟后的最大值是 \(a_{n-1} + a_n\) 第二次是 \((a_{n-1} + a_n) + a_n\) ......
循环往复，变化如同斐波那契数列，同样可以用矩阵描述
\[\begin{bmatrix}
a_1\\
b_1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_0\\
b_0
\end{bmatrix}
\]
因此，可以用矩阵快速幂计算出第一次变化后的 \(S\) 和 \(C\) 然后据此再用矩阵快速幂求出答案
代码
注意：当 \(n\) 为 \(1\) 的时候，蘑菇不会生长，直接输出 \(a_1\) 并注意取模