配点 : 100 点
解决问题后 像 Ryser 一样快速,你学会了如何计算一般图中的匹配数量 O(2^{N/2} N^2)。于是你决定写这个问题,以鼓励人们解决问题并学习新技术。
本题的时间限制和内存限制可能非常严格。对于可能造成的不便,我们深感抱歉。
問題文
无向图 求 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 的匹配是指由G 的边 k 条边组成的集合,且这些边的端点 2 k 个互不相同。)
制約
- 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).
入力
输入是按以下格式从标准输入给出的。
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}
出力
G 的大小 k 的匹配数为 2^{64} 后的余数 b_k 作为(0 \le k \le \lfloor N/2 \rfloor),请以以下格式输出。
b_0 b_1 \cdots b_{\lfloor N/2 \rfloor}
入力例 1
4 0 10 300 0 10 0 5 400 300 5 0 20 0 400 20 0
出力例 1
1 735 120200
G 的大小 2 的匹配如下。
- 頂点 1, 2 连接顶点的边中 1 条,以及顶点 3, 4 连接顶点的边中 1 由书组成的东西 200 個
- 頂点 1, 3 连接顶点的边中 1 条,以及顶点 2, 4 连接顶点的边中 1 由书组成的东西 120\,000 個
入力例 2
7 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
出力例 2
1 21 105 105
入力例 3
10 0 8629318490492529455 16934461172002342162 16689922355946803515 6532726440738276996 1194408499640297875 15866676155001669889 6498797546467110859 16876940315014902410 12387509481131737340 8629318490492529455 0 11507224725899007093 8715646015311805917 10082055328422634515 11661112510609506937 5671467989936109679 9958089075065687029 1044511129638713462 9641449008999128869 16934461172002342162 11507224725899007093 0 9017212196119468141 8742031656924741889 16712732165713258491 12486619021854068086 8079880079267306335 7411259632269635598 847494329973810398 16689922355946803515 8715646015311805917 9017212196119468141 0 16283252096557152371 8615030617835929416 17667878928797645683 18446439882335127774 11475081586957078864 15537196317840490094 6532726440738276996 10082055328422634515 8742031656924741889 16283252096557152371 0 2328769271400341339 5743580703459253102 13482125554117518013 8310663885706538154 15657502149293391713 1194408499640297875 11661112510609506937 16712732165713258491 8615030617835929416 2328769271400341339 0 13134573721194912427 3260072811817230082 12647757802949221999 15331084503094140917 15866676155001669889 5671467989936109679 12486619021854068086 17667878928797645683 5743580703459253102 13134573721194912427 0 5011674754910118042 4293452480892783480 12853153721226986708 6498797546467110859 9958089075065687029 8079880079267306335 18446439882335127774 13482125554117518013 3260072811817230082 5011674754910118042 0 8466317684966562639 13151347917827920992 16876940315014902410 1044511129638713462 7411259632269635598 11475081586957078864 8310663885706538154 12647757802949221999 4293452480892783480 8466317684966562639 0 1834230013668150904 12387509481131737340 9641449008999128869 847494329973810398 15537196317840490094 15657502149293391713 15331084503094140917 12853153721226986708 13151347917827920992 1834230013668150904 0
出力例 3
1 13998873960259808869 16134958027077044128 15075909322183550749 13815169532537848652 14625654317779811048