给定长度为n的数组a,定义一次操作为:1. 算出长度为n的数组s,使得si= (a[1] + a[2] + ... + a[i]) mod 1,000,000,007;2. 执行a = s;现在问k次操作以后a长什么样
记初始序列为$a_0$, $k$次操作后序列为$a_k$, 有
$\begin{equation}
a_k
=\begin{bmatrix}
1 & 0 & 0 &\cdots\ &0 &0\\
1 & 1 & 0 &\cdots\ &0 &0\\
1 & 1 & 1 & \cdots\ & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\
1 & 1 & 1 &\cdots\ &1& 1\\
\end{bmatrix}^k a_0
\end{equation}$
矩阵幂可以化简为
$\begin{equation}\begin{bmatrix}\binom{k-1}{0} & 0 & 0 &\cdots\ &0 &0\\\binom{k}{1} & \binom{k-1}{0} & 0 &\cdots\ &0 &0\\\binom{k+1}{2} & \binom{k}{1} &\binom{k-1}{0} & \cdots\ & 0 & 0\\\vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\\binom{k+n-2}{n-1} & \binom{k+n-3}{n-2} & \binom{k+n-4}{n-3} &\cdots\ &\binom{k}{1}& \binom{k-1}{0}\\\end{bmatrix}\end{equation}$
#include #include #include #include #include #include #include