逆元可以不存在
但是可以递推
所以可以用不需要除法的矩阵快速幂
by devans @ 2023-03-11 21:39:31
瓶颈在于取模......
by Nwayy @ 2023-03-11 21:39:54
分治
by qsceszthn @ 2023-03-11 21:40:04
分块。
by mashduihca @ 2023-03-11 21:42:21
分块。
by Harry27182 @ 2023-03-11 21:44:47
@[Untitled0](/user/393767) 分治。
by Deuteron @ 2023-03-11 21:45:52
@[mashduihca](/user/494183) 分块的话 咋统计每个块内元素和呢 不懂
by y_kx_b @ 2023-03-11 21:46:27
@[Untitled0](/user/393767) 小技巧：$10^{12}=(10^6)^2$，所以以后但凡看到 $10^{12}$ 数据范围的题都可以想是否是 $O(\sqrt{X})$ 的。（否则如果能 $O(\log)$ 或更低的复杂度计算的话，为啥要 $1e12$ 呢？）
by _Imaginary_ @ 2023-03-11 21:48:39
@[小可爱萌萌哒](/user/397982) 咋分啊
by Untitled0 @ 2023-03-11 21:50:02
@[_Imaginary_](/user/148507) 你说得对，但是这题 $O(\log X)$ 矩阵快速幂好像真能做
by Untitled0 @ 2023-03-11 21:51:46