F - Fluffian 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 800 点

「パフ」という言葉には犬の餌の意味も犬の毛玉の意味もあるそうです？ ("Pfaffian" の発音とはだいぶ違うかもしれません)

問題文

正整数 N と，2N \times 2N 整数成分交代行列 (A_{i,j}), (B_{i,j}) が与えられる (index は 1 から数える)．すなわち以下を満たす：

  • 1 \le i \le 2N に対し，A_{i,i} = 0,\, B_{i,i} = 0．
  • 1 \le i < j \le 2N に対し，A_{j,i} = -A_{i,j},\, B_{j,i} = -B_{i,j}．

(i, j) 成分を x の多項式 A_{i,j} + B_{i,j} x とする 2N \times 2N 交代行列を考える．その Pfaffian は x の高々 N 次の多項式であるが，各係数を 101 で割った余り (0 以上 101 未満) を求めよ．

制約

  • 1 \le N \le 250．
  • -101 < A_{i,j} < 101   (1 \le i, j \le 2N)．
  • -101 < B_{i,j} < 101   (1 \le i, j \le 2N)．
  • A_{i,i} = 0   (1 \le i \le 2N)．
  • B_{i,i} = 0   (1 \le i \le 2N)．
  • A_{j,i} = -A_{i,j}   (1 \le i < j \le 2N)．
  • B_{j,i} = -B_{i,j}   (1 \le i < j \le 2N)．

入力

入力は以下の形式で標準入力から与えられる．

N
A_{1,1} A_{1,2} \cdots A_{1,2N}
A_{2,1} A_{2,2} \cdots A_{2,2N}
\vdots
A_{2N,1} A_{2N,2} \cdots A_{2N,2N}
B_{1,1} B_{1,2} \cdots B_{1,2N}
B_{2,1} B_{2,2} \cdots B_{2,2N}
\vdots
B_{2N,1} B_{2N,2} \cdots B_{2N,2N}

出力

求める Pfaffian の x^k の係数 101 で割った余りを c_k として (0 \le k \le N)，以下の形式で出力せよ．

c_0 c_1 \cdots c_N

入力例 1

2
0 1 2 3
-1 0 4 5
-2 -4 0 6
-3 -5 -6 0
0 7 8 9
-7 0 10 11
-8 -10 0 12
-9 -11 -12 0

出力例 1

8 58 86

\operatorname{pf}\begin{bmatrix} 0 & 1+7x & 2+8x & 3+9x \\ -1-7x & 0 & 4+10x & 5+11x \\ -2-8x & -4-10x & 0 & 6+12x \\ -3-9x & -5-11x & -6-12x & 0 \end{bmatrix} = (1+7x)(6+12x) - (2+8x)(5+11x) + (3+9x)(4+10x) = 8 + 58x + 86x^2 である．

入力例 2

2
0 -1 -2 -3
1 0 4 5
2 -4 0 6
3 -5 -6 0
0 -7 -8 -9
7 0 10 11
8 -10 0 12
9 -11 -12 0

出力例 2

93 43 15

Pfaffian は -8 - 58x - 86x^2 となる．

入力例 3

3
0 0 0 0 0 2
0 0 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 -2 0 0 0 0
-2 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 -2 0
0 0 0 -2 0 0
0 0 2 0 0 0
0 2 0 0 0 0
0 0 0 0 0 0

出力例 3

0 93 8 0

Pfaffian は -8x + 8x^2 となる．

入力例 4

4
0 -87 100 40 31 -96 -17 -65
87 0 -73 36 82 34 -57 -99
-100 73 0 -15 -92 -35 -79 -23
-40 -36 15 0 -69 -70 -52 -11
-31 -82 92 69 0 87 -18 -39
96 -34 35 70 -87 0 55 -17
17 57 79 52 18 -55 0 30
65 99 23 11 39 17 -30 0
0 19 -63 -17 98 91 -16 45
-19 0 -88 -70 24 -31 54 44
63 88 0 4 -10 -29 -27 23
17 70 -4 0 -41 -38 -9 -81
-98 -24 10 41 0 59 -29 -48
-91 31 29 38 -59 0 8 51
16 -54 27 9 29 -8 0 14
-45 -44 -23 81 48 -51 -14 0

出力例 4

89 18 43 78 13