「CMOI R1」We Want To Run / Nilpotent
题目背景
$\small\color{white}54^{\text{th}}\text{Problem by ArCu}.$
题目描述
对于 $n\times n$ 矩阵 $A$，定义 $f(A)$ 为最小的满足 $A^b=O$ 的正整数 $b$，若不存在这样的数则 $f(A)=0$。其中 $O$ 是零矩阵，即所有元素都是 $0$ 的矩阵。
给定 $n,a$，每个元素都是 $[0,a)$ 中整数的 $n\times n$ 矩阵有 $a^{n^2}$ 种。对所有 $a^{n^2}$ 种可能的矩阵 $A$ 求 $f(A)$ 之和。
答案对 $202407031$ 取模。
输入输出格式
输入格式
一行两个整数 $n,a(1\leq n\leq 600,0<a<2^{64})$。
输出格式
一行一个整数，表示你求得的答案。
输入输出样例
输入样例 #1
2 2输出样例 #1
5输入样例 #2
3 4输出样例 #2
793输入样例 #3
5 10输出样例 #3
59350891输入样例 #4
18 15932416输出样例 #4
52138206输入样例 #5
1 1输出样例 #5
1说明
$\text{Sample 1 Explanation}:$
注意到对于任意正整数 $b$，$\begin{bmatrix}1&0\\1&1\end{bmatrix}^b\neq O$，所以 $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$。而 $\begin{bmatrix}0&0\\1&0\end{bmatrix}^2=O$，所以 $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$。
一共有 $2^4=16$ 种可能的矩阵。其中 $f(A)$ 不为 $0$ 的只有
$$f\left(\begin{bmatrix}0&0\\0&0\end{bmatrix}\right)=1,f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=f\left(\begin{bmatrix}0&1\\0&0\end{bmatrix}\right)=2$$
答案即为 $1+2+2=5$。
$\text{Details of Subtasks}:$
所有数据满足 $1\leq n\leq 600,0<a<2^{64}$。
| $\text{Subtask}$ | $\text{Special Constraints}$ | $\text{Score}$ |
| :----------: | :----------: | :----------: |
| $1$ | $n\leq 5,a\leq 2$ | $3$ |
| $2$ | $n\leq 5$ | $7$ |
| $3$ | $n\leq 10$ | $10$ |
| $4$ | $n\leq 40$ | $20$ |
| $5$ | $n\leq 200$ | $30$ |
| $6$ | | $30$ |
$\text{Hint}:202407031=13009\times 15559.$