luogu#P11173. 「CMOI R1」We Want To Run / Nilpotent

    ID: 15098 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>动态规划,dp数学2024洛谷原创O2优化动态规划优化图论建模线性代数

「CMOI R1」We Want To Run / Nilpotent

题目背景

$\small\color{white}54^{\text{th}}\text{Problem by ArCu}.$

题目描述

对于 n×nn\times n 矩阵 AA,定义 f(A)f(A) 为最小的满足 Ab=OA^b=O 的正整数 bb,若不存在这样的数则 f(A)=0f(A)=0。其中 OO 是零矩阵,即所有元素都是 00 的矩阵。

给定 n,an,a,每个元素都是 [0,a)[0,a) 中整数的 n×nn\times n 矩阵有 an2a^{n^2} 种。对所有 an2a^{n^2} 种可能的矩阵 AAf(A)f(A) 之和。

答案对 202407031202407031 取模。

输入格式

一行两个整数 n,a(1n600,0<a<264)n,a(1\leq n\leq 600,0<a<2^{64})

输出格式

一行一个整数,表示你求得的答案。

2 2
5
3 4
793
5 10
59350891
18 15932416
52138206
1 1
1

提示

Sample 1 Explanation:\text{Sample 1 Explanation}:

注意到对于任意正整数 bb[1011]bO\begin{bmatrix}1&0\\1&1\end{bmatrix}^b\neq O,所以 $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$。而 [0010]2=O\begin{bmatrix}0&0\\1&0\end{bmatrix}^2=O,所以 $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$。

一共有 24=162^4=16 种可能的矩阵。其中 f(A)f(A) 不为 00 的只有

$$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=51+2+2=5

Details of Subtasks:\text{Details of Subtasks}:

所有数据满足 1n600,0<a<2641\leq n\leq 600,0<a<2^{64}

Subtask\text{Subtask} Special Constraints\text{Special Constraints} Score\text{Score}
11 n5,a2n\leq 5,a\leq 2 33
22 n5n\leq 5 77
33 n10n\leq 10 1010
44 n40n\leq 40 2020
55 n200n\leq 200 3030
66

Hint:202407031=13009×15559.\text{Hint}:202407031=13009\times 15559.