[問題案] Power of Matrix

[Tiramister]

問題ID: matrix_pow 問題名: Power of Matrix

想定アルゴリズム: ナイーブな行列積+二分累乗法 Θ(N^3 log K)

問題概要

$N \times N$行列$A = (a{ij})$と整数$K$が与えられます。 $B = (b{ij}) = A^K$を$\bmod 998,244,353$で求めてください。

入力

N K
a_{11} a_{12} \cdots a_{1N}
a_{21} a_{22} \cdots a_{2N}
\vdots
a_{N1} a_{N2} \cdots a_{NN}

出力

b_{11} b_{12} \cdots b_{1N}
b_{21} b_{22} \cdots b_{2N}
\vdots
b_{N1} b_{N2} \cdots b_{NN}

制約

• $1 \leq N \leq 200$
• $0 \leq K \leq 10^{18}$
• $0 \leq a_{ij} \lt 998,244,353$

検討事項

• Nの大きさは適切か
• K=0の解は常に単位行列で良いか(あるいは制約から除外するか)

[yosupo06]

提案ありがとうございます！ 問題名/IDは https://judge.yosupo.jp/problem/pow_of_formal_power_series に合わせてPow of Matrix / pow_of_matrix にしておきましょう

• Nの大きさは適切か

実測次第ですが、直感的にはもう少し行けそうに思えます, 400とか, また https://yukicoder.me/wiki/black_box_linear_algebra これで更に高速化できます

• K=0の解は常に単位行列で良いか(あるいは制約から除外するか)

いいと思います

[Maruoka842]

Black Box Linear Algebra の高速化を具体的に教えてもらえないでしょうか。 以下、Nyaanさんの引用　https://twitter.com/ModInt998244353/status/1395444427867389956

最小多項式を求めた後にFiduccia's algorithmで A^k = sum_[i=0...n] ci A^i を満たす列cを求めるところまではいいんですが、結局 sum[i=0...n] c_i A^i を計算する部分をどうやって高速化するのか分からず困っています

[yosupo06]

あれ、勘違いしていました　高速化できなさそうです

[maspypy]

作業者募集