AT_xmascon22_f Fast as Fast as Ryser

无向图 $G$ 以 $1, 2, \ldots, N$ 为顶点，连接顶点 $u$ 和顶点 $v$ 的边恰好有 $A_{u,v}$ 条（$1 \le u, v \le N$）。所有的边都是区分的。 对于每个 $k = 0, 1, \ldots, \lfloor N/2 \rfloor$，请计算 $G$ 中大小为 $k$ 的匹配的个数，对 $2^{64}$ 取余。 （$G$ 中大小为 $k$ 的匹配是指包含 $k$ 条边的集合，且这些边的端点 $2k$ 个都互不相同。）

输入将以下列格式从标准输入给出。 > $N$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,N}$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,N}$ $\vdots$ $A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,N}$

对于每个 $k$（$0 \le k \le \lfloor N/2 \rfloor$），将 $G$ 中大小为 $k$ 的匹配的个数对 $2^{64}$ 取余后的结果记为 $b_k$，按如下格式输出。 > $b_0$ $b_1$ $\cdots$ $b_{\lfloor N/2 \rfloor}$

### 样例解释 1 $G$ 的大小为 $2$ 的匹配如下： - 以顶点 $1,2$ 之间的一条边和顶点 $3,4$ 之间的一条边组成的匹配有 $200$ 个。 - 以顶点 $1,3$ 之间的一条边和顶点 $2,4$ 之间的一条边组成的匹配有 $120\,000$ 个。 # 数据范围 - $1 \le N \le 40$。 - $0 \le A_{u,v} < 2^{64}$（$1 \le u, v \le N$）。 - $A_{u,u} = 0$（$1 \le u \le N$）。 - $A_{u,v} = A_{v,u}$（$1 \le u, v \le N$）。 由 ChatGPT 5 翻译