Hafnian of Matrix

AC一覧

Problem Statement問題文

Given $N \times N$ zero diagonal symmetric matrix $A = (a_{i,j})$. Print the hafnian of $A$ modulo $998{,}244{,}353$.

Constraints制約

• $2 \le N \le 38$
• $N \bmod 2 = 0$
• $0 \le a_{ij} \lt 998{,}244{,}353$
• $a_{i,i} = 0$
• $a_{i,j} = a_{j,i}$

Input入力

$N$
$a_{0,0}$ $a_{0,1}$ $\ldots$ $a_{0,N-1}$
$a_{1,0}$ $a_{1,1}$ $\ldots$ $a_{1,N-1}$
$\vdots$
$a_{N-1,0}$ $a_{N-1,1}$ $\ldots$ $a_{N-1,N-1}$


Sampleサンプル

# 1

4
0 1 2 4
1 0 3 5
2 3 0 6
4 5 6 0

28


Timelimit: 10 secs

Before submitting, please confirm terms and conditions