CF2134F.Permutation Oddness

给定四个正整数 $c_0$、$c_1$、$c_2$ 和 $c_3$。

令 $n = c_0 + c_1 + c_2 + c_3$。现在有一个长度为 $n$ 的数组 $a$，其中 $x$（$0\le x\le 3$）在 $a$ 中出现了 $c_x$ 次。对于数组 $a$ 的任意一个不同排列$^{\text{∗}}$ $b$，定义其奇异度为$^{\text{†}}$ $^{\text{‡}}$：

$$\sum_{i = 1}^{n-1} \text{lowbit}(b_i \oplus b_{i+1})$$

你的任务是，对于每一个 $k$ 从 $0$ 到 $2 \cdot (n-1)$（包含），计算出奇异度等于 $k$ 的 $a$ 的不同排列的个数。

由于答案可能非常大，只需输出对 $10^9+7$ 取模后的结果。

$^{\text{∗}}$数组的一个排列是将其所有元素按照任意顺序重新排列。例如，$[1,2,2]$ 是 $[2,2,1]$ 的一个排列，但 $[1,1,2]$ 不是。如果两个排列中存在至少一个位置不同，则认为它们是不同的。

$^{\text{†}}$ $\oplus$ 表示按位异或运算。

$^{\text{‡}}$ $\text{lowbit}(x)$ 为 $x$ 的二进制下最低位（即最低的非零位对应的 $2^k$），例如 $\text{lowbit}(12)=4$，$\text{lowbit}(8)=8$。特别地，规定 $\text{lowbit}(0)=0$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。每组测试用例一行，包含四个正整数 $c_0$、$c_1$、$c_2$ 和 $c_3$（$1 \le c_0, c_1, c_2, c_3 < 800$，$4 \le c_0 + c_1 + c_2 + c_3 \le 800$）。

令 $n = c_0 + c_1 + c_2 + c_3$。保证所有测试用例的 $n$ 之和不超过 $800$。

对于每个测试用例，输出一行 $2 \cdot (n-1) + 1$ 个整数，分别表示奇异度为 $0,1,\ldots, 2 \cdot (n-1)$ 的不同排列数，答案对 $10^9+7$ 取模。

在第一个测试用例中，数组 $a$ 有 $24$ 个不同排列。下表为部分排列的奇异度值：

排列	奇异度
$[0,1,2,3]$	$\text{lowbit}(0 \oplus 1) + \text{lowbit}(1 \oplus 2) + \text{lowbit}(2 \oplus 3) = 1 + 1 + 1 = 3$
$[0,2,1,3]$	$\text{lowbit}(0 \oplus 2) + \text{lowbit}(2 \oplus 1) + \text{lowbit}(1 \oplus 3) = 2 + 1 + 2 = 5$
$[0,1,3,2]$	$\text{lowbit}(0 \oplus 1) + \text{lowbit}(1 \oplus 3) + \text{lowbit}(3 \oplus 2) = 1 + 2 + 1 = 4$

统计这 $24$ 个排列：

• 有 $8$ 个排列奇异度为 $3$。
• 有 $8$ 个排列奇异度为 $4$。
• 有 $8$ 个排列奇异度为 $5$。

在第二个测试用例中，数组 $a$ 的不同排列数为 $840$，奇异度分布如下：

• $8$ 个排列奇异度为 $3$。
• $32$ 个排列奇异度为 $4$。
• $126$ 个排列奇异度为 $5$。
• $184$ 个排列奇异度为 $6$。
• $244$ 个排列奇异度为 $7$。
• $156$ 个排列奇异度为 $8$。
• $72$ 个排列奇异度为 $9$。
• $18$ 个排列奇异度为 $10$。

由 ChatGPT 5 翻译