#P18652. Exact Subsequences
Exact Subsequences
Exact Subsequences
考虑所有恰好具有 个不同非空子序列的二进制字符串。这里不同按子序列的内容区分,同一内容从不同位置选取得到时只计一次。将这些字符串按字典序从小到大排序,请求出第 个字符串。
子序列指从字符串中删除若干字符(也可以不删除),保持其余字符的相对顺序后得到的字符串。字典序按 比较;若一个字符串是另一个的真前缀,则较短者在前。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例占一行,包含两个整数 ()。
输出格式
对每个测试用例,如果满足要求的二进制字符串不足 个,输出一行 -1。
否则,输出字典序第 个字符串的游程编码,占两行:
第一行输出 和 ,其中 是极大连续相同字符段的数量, 是第一段的字符(0 或 1)。
第二行依次输出这 段的长度 。各长度均为正整数,相邻段的字符交替变化。例如 000110 的表示为第一行“3 0”、第二行“3 2 1”。每个非空二进制串的这种表示唯一。
样例输入 1
8
3 1
3 2
3 3
3 4
3 5
1000000000 1
99824 4353
2129721 207087
样例输出 1
1 0
3
2 0
1 1
2 1
1 1
1 1
3
-1
1 0
1000000000
11 0
9 2 2 1 6 2 1 2 7 1 1
9 0
9 9 8 2 4 4 3 5 3
样例说明
八个测试用例对应的实际字符串依次为:
000
01
10
111
-1
000...000(共 1000000000 个 0)
0000000001100100000011011000000010
00000000011111111100000000110000111100011111000
第六行的省略写法仅用于说明;程序必须输出样例输出中的游程编码,不能输出省略号。第五个用例不存在答案。