← 返回题目列表

Codeforces · 2134/F

F. 排列奇数

中文机器翻译题面 查看原题

给定四个正整数 $$$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$$$) 出现 $$$c_x$$$ 次。对于任何 不同的排列$$$^{\text{*}}$$$ $$$b$$$ 的数组$$$a$$$,定义其 奇怪 as$$$^{\text{†}}$$$$$$^{\text{‡}}$$$:

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

你的任务是,对于从 $$$0$$$ 到 $$$2 \cdot (n-1)$$$(含)的每个整数 $$$k$$$,计算奇数等于 $$$k$$$ 的 $$$a$$$ 的不同排列的数量。

由于数字可能太大,您只需对 $$$10^9 + 7$$$ 求模即可。

$$$^{\text{*}}$$$数组的排列是将其元素排列成任意顺序。例如,$$$[1,2,2]$$$ 是 $$$[2,2,1]$$$ 的排列,但 $$$[1,1,2]$$$ 不是。如果两个排列至少在一个位置不同,则认为它们是不同的。

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

$$$^{\text{‡}}$$$$$$\text{lowbit}(x)$$$ 是 $$$x$$$ 的最低二进制位的值,例如$$$\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 \lt 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$$$ 整数 - $$$a$$$ 的不同排列的数量,奇数分别等于 $$$0,1,\ldots, 2 \cdot (n-1)$$$。输出对 $$$10^9+7$$$ 取模的答案。

示例

输入
复制

3
1 1 1 1
1 2 4 1
3 3 3 3

输出
复制

0 0 0 8 8 8 0
0 0 0 8 32 126 184 244 156 72 18 0 0 0 0
0 0 0 8 56 424 1472 5760 12128 29376 40384 65232 59920 65232 40384 29376 12128 5760 1472 424 56 8 0

注意

在第一个测试用例中,数组 $$$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$$$。