AT_xmascon22_f.Fast as Fast as Ryser

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

无向图 $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

输出#1

1 735 120200

输入#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

说明/提示

样例解释 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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页