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$.

対角成分が $0$ の $N \times N$ 対称行列 $A = (a_{i,j})$ が与えられます。$A$ のハフニアンを mod $998{,}244{,}353$ で求めてください。

Constraints
制約

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

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions