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$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 $^{\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 翻译