题解：AT_arc133_f [ARC133F] Random Transition

· · 题解

萌新第一道独立做出的问号题，纪念一下。虽然是个不用动脑子的题。

给题解区补充一个对角化做法。

接下来行、列、特征值的标号为 0\sim n。

这个题面一看显然就是对角化，所以直接把转移矩阵搞出来：A_{i+1,i}=1-\frac in,A_{i,i+1}=\frac {i+1}n，那么我们显然是不会手算特征值的，随便找一个找一个特征值计算器可以得到第 i 个特征值是 \lambda_i=1-2\frac in。

发现特征向量就没有很好的规律了，除了两列二项式系数什么都观察不到。发现矩阵非常稀疏，所以直接列出关于特征向量的方程，得到第 m 个特征向量满足

(n-2m)f_{m,i}=(n-(i-1))f_{m,i-1}+(i+1)f_{m,i+1}

这是一个非常标准的整式递推的形式，写成幂级数的形式可以得到

(2m+nx-n)F_m=(x^2-1)F_m'

简单分离变量即可解出这个微分方程：

\begin{aligned} &\frac{F_m'}{F_m}=\frac{2m+nx-n}{x^2-1}\\ \implies&\ln F_m=(n-m)\ln(x+1)+m\ln(x-1)\\ \implies&F_m=(1+x)^{n-m}(1-x)^m \end{aligned}

这样就能将 A 分解成 XDX^{-1} 的形式了，D 的对角线上是所有的特征值，X 的第 m 列则是对应 \lambda_m 的特征向量 F_m。

现在需要计算 \mathbf w=X\mathbf v，直接将 F_m 带入就得到

W(x)=(1+x)^nV\left(\frac{1-x}{1+x}\right)

计算 \mathbf v=X^{-1}\mathbf w 相当于知 W 求 V：

2^{-n}(1+x)^{n}W\left(\frac{1-x}{1+x}\right)=V(x)

计算 V\left(\dfrac{1-x}{1+x}\right) 可以使用这个方法。这样就做完了。