#P16119. [2026年山东集训一轮]路径很爽

[2026年山东集训一轮]路径很爽

题目描述

给定一张有 nn 个节点和 n(n−1)2\dfrac{n(n-1)}2 条边的无向完全图。每条边 (i,j)(i,j) 带权:

Wi,j∈{0,1}.W_{i,j}\in\{0,1\}.

对于所有 0≤s<2n−10\le s<2^{n-1},计数满足下列条件的排列 pp 的数量 VsV_s:

对所有 i∈[1,n−1]i\in[1,n-1],都有

$$W_{p_i,p_{i+1}} =\left\lfloor \frac{s}{2^{i-1}}\right\rfloor \bmod 2.$$

也就是说,ss 的二进制第 i−1i-1 位规定了路径上第 ii 条边的颜色。你需要对每一种长度为 n−1n-1 的 0/10/1 边权序列,统计有多少个点排列的相邻边权序列恰好等于它。

输入格式

第一行一个整数 nn。

接下来 nn 行,第 ii 行 nn 个整数,第 jj 个表示 Wi,jW_{i,j}。

保证 Wi,j=Wj,iW_{i,j}=W_{j,i},Wi,iW_{i,i} 恒为 00 且没有实际意义。

输出格式

输出一行 2n−12^{n-1} 个整数,第 ii 个整数为 Vi−1V_{i-1}。

样例 1

输入

3
011
101
110

输出

0 0 0 6

样例 2

输入

4
0101
1000
0001
1010

输出

2 2 6 2 2 6 2 2

数据范围与约定

对于所有测试数据,满足:

1≤n≤19.1\le n\le 19.
子任务编号 特殊性质 分值
1 n≤10n\le 10 10
2 n≤14n\le 14 20
3 n≤15n\le 15 10
4 n≤16n\le 16 15
5 n≤17n\le 17
6 n≤18n\le 18
7 n≤19n\le 19