题目背景
$\small\color{white}54^{\text{th}}\text{Problem by ArCu}.$
题目描述
对于 n×n 矩阵 A,定义 f(A) 为最小的满足 Ab=O 的正整数 b,若不存在这样的数则 f(A)=0。其中 O 是零矩阵,即所有元素都是 0 的矩阵。
给定 n,a,每个元素都是 [0,a) 中整数的 n×n 矩阵有 an2 种。对所有 an2 种可能的矩阵 A 求 f(A) 之和。
答案对 202407031 取模。
输入格式
一行两个整数 n,a(1≤n≤600,0<a<264)。
输出格式
一行一个整数,表示你求得的答案。
2 2
5
3 4
793
5 10
59350891
18 15932416
52138206
1 1
1
提示
Sample 1 Explanation:
注意到对于任意正整数 b,[1101]b=O,所以 $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$。而 [0100]2=O,所以 $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$。
一共有 24=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。
Details of Subtasks:
所有数据满足 1≤n≤600,0<a<264。
Subtask |
Special Constraints |
Score |
1 |
n≤5,a≤2 |
3 |
2 |
n≤5 |
7 |
3 |
n≤10 |
10 |
4 |
n≤40 |
20 |
5 |
n≤200 |
30 |
6 |
|
Hint:202407031=13009×15559.