分数: 650 点
问题陈述
有 16 整数元组 (A, B, C, D) 满意 A, B, C, D \in \lbrace 0, 1 \rbrace。对于他们每个人,解决以下问题。
非空字符串 S 组成
0和1满足以下条件时称为漂亮字符串:
- (条件)您可以执行以下操作序列,直到长度达到 S 变为 分别为 1 并使唯一剩余的字符 S be
1.
- 选择任意整数 i 满意 1 \leq i \leq |S| - 1.
- 定义一个整数 x 如下:
- If S_i =
0和 S_{i+1} =0,让 x = A.- If S_i =
0和 S_{i+1} =1,让 x = B.- If S_i =
1和 S_{i+1} =0,让 x = C.- If S_i =
1和 S_{i+1} =1,让 x = D.- 删除 S_i 和 S_{i+1},并插入对应的数字 x 代替他们。
例如,如果 牌匾上写着 S=10101然后你选择 i=2,运算后的字符串为1001if B=0,和1101if B=1.给你一个字符串 T 长度 N 组成
0和1.
- 让 L 是最长的美丽字符串的长度,它是以下字符串的子串 T (如果没有子字符串 T 是一个漂亮的字符串,让 L = -1),
- 让 M 是作为子串的漂亮字符串的数量 T.
查找 L 和 M。即使两个子字符串与字符串相同,如果它们取自不同的位置,也要单独计数。
什么是子字符串?
A 子字符串 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.例如,
10 是一个子串 101,但是 11 不是以下的子串 101.
约束
- 1 \leq N \leq 2 \times 10^5
- N 是一个整数。
- T 是一个长度为 N 组成
0和1.
输入
输入由标准输入按以下格式给出:
N T
输出
打印 16 行。的 i- 第行应包含 L 和 M 用空格分隔 (A,B,C,D) 满意 i-1 = 8A + 4B + 2C + D.
示例输入 1
3 110
示例输出 1
1 2 2 3 2 3 3 5 1 2 2 3 2 3 3 5 3 3 2 3 3 4 3 5 3 3 2 3 3 4 3 5
我们解释一下这个案例 (A,B,C,D)=(0,0,0,1).
字符串 11 通过取第一个到第二个字符获得 T 是一个漂亮的字符串,因为如果你选择 i=1 并执行操作,字符串变为 1.
在这种情况下 (A,B,C,D)=(0,0,0,1),美丽的字符串,是 T 是以下三个字符串:
- 字符串
1通过取第一个字符获得 T. - 字符串
1通过取第二个字符获得 T. - 字符串
11通过取第一个到第二个字符获得 T.
示例输入 2
4 0000
示例输出 2
-1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 4 4 4 4 4 6 4 6 4 6 4 6 4 6 4 6
示例输入 3
30 011011100101110111100010011010
示例输出 3
1 17 4 31 29 263 29 280 29 232 29 247 30 240 30 447 30 418 29 225 30 435 30 435 30 435 30 435 30 439 30 452