行列級数 C編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
これまでの問題では、行列 A の k 乗を計算してきました。
実は、行列 A に対して、A + A^2 + A^3 + ... + A^k のような和を高速に計算する方法も存在します。
ここで、n × n の行列のブロックを 2 × 2 個もった大きな行列を考えると、以下のような性質が成り立ちます。
[[A, O], [I, I]]^k = [[A^k, O], [I + A + A^2 + ... + A^{k-1}, I]]
ここで、[[A, O], [I, I]] は 2n × 2n の行列で、
A は n × n の行列、
O はすべての要素が 0 の n × n の行列、
I は I_{ii} = 1 であり、それ以外の要素が 0 の n × n の行列です。
実際に変数で表すと、
[[A, O], [I, I]] =
[[a_{11}, a_{12}, ..., a_{1n}, 0, 0, ..., 0],
[a_{21}, a_{22}, ..., a_{2n}, 0, 0, ..., 0],
...
[a_{n1}, a_{n2}, ..., a_{nn}, 0, 0, ..., 0],
[1, 0, ..., 0, 1, 0, ..., 0],
[0, 1, ..., 0, 0, 1, ..., 0],
...
[0, 0, ..., 1, 0, 0, ..., 1]]
となります。
この性質により、[[A, O], [I, I]]^{k + 1} の左下 n × n の部分が I + A + A^2 + A^3 + ... + A^k に対応します。
最後に単位行列 I を引くことで、A + A^2 + A^3 + ... + A^k を求めることができます。
これを利用して、行列 A に対して A + A^2 + A^3 + ... + A^k を高速に計算してください。
ただし、答えは非常に大きくなる可能性があるため、10000000 = 10^7 で割ったあまりを出力してください。
- 入力される値
-
n k
a_{11} a_{12} ... a_{1n}
a_{21} a_{22} ... a_{2n}
...
a_{n1} a_{n2} ... a_{nn}
・ 1 行目に整数 n と整数 k が半角スペース区切りで与えられます。
・ 続く n 行には、行列 a の各行の要素が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
合計 n 行出力してください。
i 行目には、A + A^2 + A^3 + ... + A^k の i 行目の要素を半角スペース区切りで出力してください。
ただし、それぞれの要素は 10000000 = 10^7 で割ったあまりを出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 100
・ 1 ≦ k ≦ 2^20
・ 0 ≦ a_{ij} ≦ 100 (1 ≦ i, j ≦ n)
- 入力例1
-
2 2
1 2
3 4
- 出力例1
-
8 12
18 26
- 入力例2
-
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
- 出力例2
-
85 85 85 85
85 85 85 85
85 85 85 85
85 85 85 85
