网站建设公司前台,做黑网站赚钱吗,柳州网站建站费用,网站建设 力洋网络矩阵对角化 今天听 \(\texttt{m}\color{red}\texttt{yee}\) 嘴的#xff0c;赶紧来补个学习笔记。 我们有点时候需要计算一个较小矩阵的 \(n\) 次幂#xff0c;但直接求幂非常不方便#xff0c;这是会考虑矩阵对角化#xff0c;将 \(M\) 改写为 \(\mathcal{PDP^{-1}}\)赶紧来补个学习笔记。 我们有点时候需要计算一个较小矩阵的 \(n\) 次幂但直接求幂非常不方便这是会考虑矩阵对角化将 \(M\) 改写为 \(\mathcal{PDP^{-1}}\)这样 \(M^n\) 次就可以写为 \((\mathcal{PDP^{-1}})\mathcal{PD^nP^{-1}}\)转化为快速计算 \(\mathcal{D^n}\)。 求解方法 我们定义一个矩阵 \(\mathcal{A}\) 的特征向量为 \(\alpha\)相应特征值为 \(\gamma\)他们满足 \[\mathcal{A}\alpha\gamma\alpha \]其中 \(\alpha\) 是定义在 \(K^n\) 次空间内的非零向量\(\gamma\) 是一个常数可以将上面的式子写成矩阵的形式 \[\begin{bmatrix}a_{1,1}a_{1,2}\cdotsa_{1,m}\\a_{2,1}a_{2,2}\cdotsa_{2,m}\\\vdots\vdots\ddots\vdots\\a_{n,1}a_{n,2}\cdotsa_{n,m}\end{bmatrix}\times\begin{bmatrix}b_1\\b_2\\\vdots\\b_n\end{bmatrix}\begin{bmatrix}\gamma b_1\\\gamma b_2\\\vdots\\\gamma b_n\end{bmatrix} \]矩阵对这个向量只起到拉扯作用。 对于上面的定义式 \(\mathcal{A}\alpha\gamma\alpha\)我们在右边乘上一个 \(I\) 单位矩阵对答案不会有任何影响并可以作一下变形 \[\mathcal{A}\alpha\gamma\mathcal{I}\alpha\\ (\mathcal{A}-\gamma\mathcal{I})\alpha\vec{0}\\ \]观察上面的式子可以发现 \(\mathcal{A}-\gamma\mathcal{I}\) 一定不存在矩阵的逆(证明如果存在可以在等式左右两端各乘上一个逆那么得到 \(\alpha\vec{0}\)但由于 \(\alpha\not\vec{0}\)矛盾所以不行)。 由于不存在矩阵的逆所以一定有 \(\text{det}(\mathcal{A}-\gamma\mathcal{I})0\) 那么根据行列式的定义式 \[\text{det}(M)\sum_{\{p\}}(-1)^{\sigma(\{p\})}\prod_{i1}^na_{i,p_i} \]我们不妨手动计算行列式其中不失有对二、三阶矩阵行列式的快速计算方法 二阶矩阵行列式主对角线元素之积减去另外两个元素的乘积。三阶矩阵行列为主对角线三乘三减去副对角线三乘三\(a_{11}a_{22}a_{33}a_{12}a_{23}a_{31}a_{13}a_{21}a_{32}-a_{13}a_{22}a_{31}-a_{12}a_{21}a_{33}-a_{11}a_{23}a_{32}\)。 为了防止忘记减去 \(\gamma\)我们将 \(\mathcal{A}-\gamma\mathcal{I}\) 写成矩阵形式这就是我们需要求解的矩阵 \[\begin{bmatrix}a_{1,1}-\gammaa_{1,2}\cdotsa_{1,m}\\a_{2,1}a_{2,2}-\gamma\cdotsa_{2,m}\\\vdots\vdots\ddots\vdots\\a_{n,1}a_{n,2}\cdotsa_{n,m}-\gamma\end{bmatrix} \]那么写出行列式表达式我们得到了关于 \(\gamma\) 的一个方程对它求解我们就得到了 \(\le n\) 个 \(\gamma\) 值。 对于每一个 \(\gamma\)代回上面 \((\mathcal{A}-\gamma\mathcal{I})\alpha\vec{0}\) 的式子我们就可以计算出 \(n\) 个 \(\alpha\) 的表达式我们的要求是这 \(n\) 个 \(\alpha\) 线性无关 结果已经出现假设对角化后结果为 \(\mathcal{A}\mathcal{PDP^{-1}}\)那么 \[\mathcal{P}\begin{bmatrix}\alpha_1\alpha_2\cdots\alpha_n\end{bmatrix}\\\mathcal{D}\begin{bmatrix}\gamma_10\cdots0\\0\gamma_2\cdots0\\\vdots\vdots\ddots\vdots\\00\cdots\gamma_n\end{bmatrix} \]\(\mathcal{P^{-1}}\) 就是 \(\mathcal{P}\) 的逆可以手动计算由于 \(\gamma\) 解 \(\alpha\) 时可能会有多个解只要相应 \(\gamma\) 对应相应 \(\alpha\) 即可。 注意其中每一个 \(\alpha\) 都是列向量所以 \(\mathcal{P}\) 是一个 \(n\times n\) 的方阵。 这样就可以快速求出 \(\mathcal{A}\) 的表达式啦 例题 hdu 6956 Pass! 有 \(n\) 个小朋友在玩球最开始球在 \(1\) 号小朋友手上每次游戏小朋友都会将球等概率传给除了自己的任何一个小朋友。 设经过 \(t\) 次传球后将球传回 \(1\) 号小朋友的方案数对 998244353 取模的值为 \(x\)。 现在给定 \(x\)求最小的 \(t\)满足方案数取模后为 \(x\)如果无解输出 -1。 \(1\le T\le 100,2\le n\le 10^6,0\le x998244353\)。 先考虑一个正向暴力的做法 \[dp_{i,j}\dfrac{\sum_{k1}^{n}[j\notk]dp_{i-1,k}}{n-1}\\ \]设 \(f_i\) 表示在第 \(i\) 次传球后球在 \(1\) 的概率\(g_i\) 表示不在 \(1\) 的概率一定有 \(f_ig_i1\) \[g_{i}(n-2)\times g_{i-1}(n-1)\times f_{i-1}\\ f_ig_{i-1}\\ \begin{bmatrix}f_0\\g_0\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}\\ \begin{bmatrix}f_i\\g_i\end{bmatrix}\begin{bmatrix}01\\n-1n-2\end{bmatrix}\times \begin{bmatrix}f_{i-1}\\g_{i-1}\end{bmatrix}\begin{bmatrix}01\\n-1n-2\end{bmatrix}^i\times \begin{bmatrix}1\\0\end{bmatrix} \]根据上面的推导我们对等式右边的矩阵对角化可以解出 \(\gamma_1n-1,\gamma_2-1\) \[\alpha_1\begin{bmatrix}n-1\\1\end{bmatrix}\\ \alpha_2\begin{bmatrix}1\\-1\end{bmatrix}\\ \]写出对角化之后的矩阵 \[\mathcal{P}\begin{bmatrix}n-11\\1-1\end{bmatrix}\\ \mathcal{D}\begin{bmatrix}n-10\\0-1\end{bmatrix}\\ \mathcal{P^{-1}}\begin{bmatrix}gugugu\end{bmatrix} \]
