给定 n \times n 的矩阵 \textbf A，让你判断是否存在非负整数 p 使得 \textbf A ^ p 为 \textbf 0。
实际上，直接判断 \textbf A ^ n 是否为 \textbf 0 即可。
考虑证明：Cayley-Hamilton 定理指出，矩阵 \textbf {A} 的特征多项式 f(\lambda) = |\lambda \textbf I - \textbf A| 为其化零多项式，即 f(\textbf A) = \textbf 0。从而我们可以知道若 R_p(\lambda) = \lambda ^ p \bmod f(\lambda)，则 \textbf A ^ p = R_p(\textbf A)。这实际上是一个线性递推的形式，而这个线性递推的特征多项式即为 f(\lambda)。众所周知，线性递推可以被写成 \frac {P(x)} {Q(x)} 的形式，且 P(x), Q(x) 的次数不超过线性递推的阶数。而题目条件即为要求 \frac {P(x)} {Q(x)} 项数有限，此时必然有 Q(x) \mid P(x)，而又因为 \text {deg } P(x) < n，因此这个递推一定在第 n 项处就已经开始取值为 0。于是只需判断 \textbf A ^ n 是否为 \textbf 0 即可。
具体实现上，可以考虑找一个大质数 P，计算 \textbf A ^ n 在模 P 意义下的取值。随机选取 P 可以保证正确性，当然数据没有对着任何模数卡。复杂度 O(T n ^ 3 \log n)，但是常数比较小，可以轻松通过。如果你对这些 trick 比较熟练，也一定可以想到随机一个向量 \textbf v，检查 \textbf v \cdot \textbf A^ n 是否为 \textbf 0，这样可以做到 O(T n ^ 3)。