#2254. 斯芬克斯的谜题
斯芬克斯的谜题
斯芬克斯的谜题
题目描述
标题: 斯芬克斯的谜题 - Problem - QOJ.ac
#17585. 斯芬克斯的谜题
The problem was used in the following contests:
题目描述
斯芬克斯为你准备了一个谜题。
斯芬克斯手中有一个不含零的可重集 A,A 的 2|A| 个子集的和构成了一个可重集 B,B 可以拆成若个二元组 (xi,yi) 表示元素 xi 的出现次数为 yi。
坏心思的斯芬克斯只把最后的 (xi,yi) 交给了你。
聪明的你注意到根据给定信息还原出的 A 的本质不同的方案可能比较多,于是你想知道可以还原出的 A 的本质不同方案数方案数模 998244353 和字典序最小的可还原 A。
保证对于给定的 (xi,yi),一定存在一个合法的 A。
我们称两个集合 A, B 本质不同,当且仅当存在一个元素在 A 中出现次数跟 B 中出现次数不同。
输入格式
第一行输入一个正整数 n,表示二元组大小。
接下来 n 行,每行输入两个整数 xi,yi,表示给定的二元组。
输出格式
第一行输出本质不同的方案数模 998244353 的结果。
第二行输出一个整数 n,表示字典序最小的 A 的长度。
第三行输出 n 个整数,字典序最小的 A 的内容。元素应当按照从小到大的顺序输出。两个集合的字典序比较是将集合元素从小到大排序后形成的序列的字典序比较。
注意:如果你对于所有的数据,第一行的输出均正确,可以获得该测试点 25% 的分数。但是如果你只要这个部分分,你也要输出格式合法。第一行错误不给分。
样例一
input
3
0 1
1 2
2 1
output
1
2
1 1
样例二
input
5
-2 1
-1 2
0 2
1 2
2 1
output
2
3
-2 1 1
explanation
样例 1 的合法的 A 为 {1,1}。
样例 2 的合法的 A 为 {−2,1,1} 或 {−1,−1,2}。
限制与约定
对于所有数据,保证 1≤n≤105,−1013≤xi≤1013,1≤yi≤1013,xi 互不相同。
本题有 4 个子任务。一个子任务的得分是其中测试点得分的最小值。
子任务编号 子任务分数 特殊限制 1 16 n≤10 2 8 xi≥0 3 32 n≤100 4 44 无特殊限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
0 1
1 2
2 1
1
2
1 1
样例 2
5
-2 1
-1 2
0 2
1 2
2 1
2
3
-2 1 1