无需脑子，背式子即可，可惜是 $O(n^4)$

我们都知道根据 $\text{Cayley-Hamilton}$ 定理有

$$\sum_{i=0}^n c_i A^i=\text{O}$$

$O$ 是 $0$ 矩阵

令 $C_i=c_{n-i}$ ， $s_i$ 为 $A^i$ 对角线上数的和

所以根据牛顿恒等式（我也不知道咋来的，推导咕咕咕）就有：

$$\sum_{i=0}^{k-1}C_i S_{k-i}+k C_k=0$$

完结撒花（又水了一篇博客）