← 返回题目列表

Codeforces · 2211/B

B. 米老鼠建设性

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

给定一个数组 $$$a$$$,令 $$$f(a)$$$ 为将 $$$a$$$ 划分为一个或多个子数组 $$$^{\text{*}}$$$ 的方法数量,使得:

  • 每个元素恰好出现在一个子数组中。
  • 所有子数组具有相同的总和。

例如,如果$$$a=[1,1]$$$,则$$$f(a)=2$$$,因为有两种这样的方式来划分$$$[1,1]$$$:

  • $$$[1,1]$$$,其中唯一的子数组的总和为 $$$2$$$。
  • $$$[1]+[1]$$$,其中两个子数组的总和为 $$$1$$$。

给你两个整数 $$$x$$$ 和 $$$y$$$。在长度为 $$$x+y$$$ 的所有数组 $$$f(a)$$$ 上查找 $$$f(a)$$$ 的最小值,该数组由数字 $$$1$$$ 的 $$$x$$$ 副本和按某种顺序的数字 $$$-1$$$ 的 $$$y$$$ 副本组成。由于这个答案可能很大,因此输出对 $$$676\,767\,677$$$ 取模的答案。此外,您应该构造一个数组来实现这一最小值。

$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$c$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$c$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \leq x,y \leq 2\cdot 10^5$$$)。保证$$$x+y \geq 1$$$。

保证所有测试用例的$$$x$$$总和不超过$$$2\cdot 10^5$$$,所有测试用例的$$$y$$$总和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出两行:所有有效数组 $$$a$$$ 对 $$$676\,767\,677$$$ 取模的 $$$f(a)$$$ 的最小值,以及达到最小结果的数组示例。请注意,您正在最小化 $$$f(a)$$$,并以该最小值对 $$$676\,767\,677$$$ 取模,而不是找到 $$$f(a)$$$ mod $$$676\,767\,677$$$ 的最小可能结果。

示例

输入
复制

4
2 0
1 1
6 7
1 3

输出
复制

2
1 1
1
1 -1
1
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
2
-1 -1 -1 1

注意

在第一个测试用例中,$$$x=2$$$ 和 $$$y=0$$$。唯一可能的数组是 $$$a=[1,1]$$$,其中 $$$f(a)=2$$$ 如上所述。

在第二种情况下,$$$x=1$$$ 和 $$$y=1$$$。最小化 $$$f(a)$$$ 的一种可能的数组是 $$$a=[1,-1]$$$,其中 $$$f(a)=1$$$ (作为划分为所有子数组具有相等总和的子数组的唯一方法是 $$$[[1,-1]]$$$)。