問題一覧 > 通常問題

No.1907 DETERMINATION

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : 👑 hitonanodehitonanode / テスター : SumitacchanSumitacchan
2 ProblemId : 7711 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:18:16

問題文

$\mathbb{F}_{998244353}$ 上の $N$ 次正方行列 $M_0, M_1$ が与えられます．$x$ を不定元として，行列 $M_0 + M_1 x$ の行列式 $\sum_{k=0}^N a_k x^k$ の各係数 $a_0, \dots, a_N$ を求めてください．

入力

$N$
$M_{011} \; M_{012} \; \dots \; M_{01N}$
$\vdots$
$M_{0N1} \; M_{0N2} \; \dots \; M_{0NN}$
$M_{111} \; M_{112} \; \dots \; M_{11N}$
$\vdots$
$M_{1N1} \; M_{1N2} \; \dots \; M_{1NN}$

  • $1 \le N \le 400$
  • $0 \le M_{dij} \le 998244352$ （$0 \le d \le 1, 1 \le i \le N, 1 \le j \le N$）
  • 入力は全て整数

出力

$N + 1$ 行にわたって出力してください．$i$ 行目（$1 \le i \le N + 1$）には $a_{i - 1}$ の値を $0 \le a_{i - 1} \le 998244352$ の範囲で出力してください．最終行でも改行してください．

サンプル

サンプル1
入力
2
1 4
2 3
1 0
0 1
出力
998244348
4
1

行列 $\begin{pmatrix} x + 1 & 4 \\ 2 & x + 3 \end{pmatrix}$ の行列式を求めます．計算すると，$(x + 1)(x + 3) - 2 \cdot 4 = x^2 + 4x - 5 = x^2 + 4x + 998244348$ です．

サンプル2
入力
2
0 0
2 3
1 5
1 1
出力
0
998244346
998244349

サンプル3
入力
5
39 47 33 40 34
14 28 50 39 44
56 70 56 63 56
35 49 53 51 50
10 16 22 19 20
34 24 28 53 31
21 15 18 33 20
35 27 38 58 43
50 36 44 79 49
8 6 8 13 9
出力
0
0
0
0
0
0

サンプル4
入力
10
10564 15278 11953 16394 14961 16552 11083 11008 18397 11438
5364 14524 8257 8680 14016 11094 8007 9591 14231 7815
10846 18308 13608 12810 19149 16310 10482 13183 21980 9293
8186 15433 12809 12082 9156 11902 8494 14051 15591 10025
9841 16226 10653 16842 10450 13182 10483 13917 21382 10495
5726 8371 6060 4708 10824 7774 3035 6493 11704 5429
11804 21620 12523 12824 19448 14904 7255 15497 26017 15621
5967 9775 5399 5043 4770 3385 2101 6686 12752 5451
7645 11308 8478 13586 14503 15210 8710 9555 14631 10793
12322 22689 17303 16847 15707 17089 12597 16067 22215 13884
11408 8049 10519 10127 11994 15275 7414 12402 11393 5668
25825 19279 16231 15676 25964 29972 13830 16143 23087 11117
25187 23547 18728 16718 26475 28570 9990 17669 19592 8984
30516 18710 22791 20149 19036 23821 12261 23637 19604 17708
21525 13105 13689 12195 14736 17778 8704 14352 14131 12003
20385 15744 16251 14793 19910 24272 10809 16152 19332 9252
24117 21421 22605 18342 22447 27025 10348 21192 22573 9681
25252 16080 23049 19342 17928 24785 12433 23891 22644 14251
28308 16070 19811 18546 19757 24204 13973 22758 19516 15901
18217 15911 8766 8827 16819 15552 6213 7067 9755 6427
出力
0
0
0
555404909
435862997
527181218
541789574
308208298
0
0
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。