AT_abc418_g.[ABC418G] Binary Operation

共有 $16$ 个整数元组 $(A, B, C, D)$ 满足 $A, B, C, D \in \lbrace 0, 1 \rbrace$。对于每一个元组，解决如下问题。

给定一个只由 0 和 1 组成的非空字符串 $S$，当且仅当满足以下条件时，称 $S$ 为美丽字符串：

• （条件）你可以反复执行以下操作，直到 $S$ 的长度变为 $1$，并且最终剩下的唯一字符为 1。
  1. 任选一个整数 $i$，满足 $1 \leq i \leq |S| - 1$。
  2. 按如下方式定义整数 $x$：
     • 如果 $S_i = $ 0 且 $S_{i+1} = $ 0，则 $x = A$。
     • 如果 $S_i = $ 0 且 $S_{i+1} = $ 1，则 $x = B$。
     • 如果 $S_i = $ 1 且 $S_{i+1} = $ 0，则 $x = C$。
     • 如果 $S_i = $ 1 且 $S_{i+1} = $ 1，则 $x = D$。
  3. 删除 $S_i$ 和 $S_{i+1}$，并在它们的位置插入对应于 $x$ 的数字。
     例如，如果 $S = $ 10101 且你选择 $i = 2$，则操作后字符串为 1001（若 $B = 0$），或 1101（若 $B = 1$）。

给定一个长度为 $N$ 的只由 0 和 1 组成的字符串 $T$。

• 令 $L$ 为 $T$ 的所有子串中最长的美丽字符串的长度（若 $T$ 的所有子串都不是美丽字符串，则 $L = -1$）。
• 令 $M$ 为 $T$ 的所有子串中美丽字符串的个数。

求 $L$ 和 $M$。即使两个子串内容相同，只要它们在 $T$ 中的位置不同，也要分别计数。

什么是子串？一个字符串 $S$ 的子串是通过从 $S$ 的开头删除零个或多个字符、从结尾删除零个或多个字符得到的字符串。
例如，10 是 101 的子串，但 11 不是 101 的子串。

输入按如下格式从标准输入读入：

$N$ $T$

输出 $16$ 行。第 $i$ 行应输出对应于满足 $i-1 = 8A + 4B + 2C + D$ 的 $(A,B,C,D)$ 的 $L$ 和 $M$，用空格分隔。

样例解释 1

以 $(A,B,C,D)=(0,0,0,1)$ 为例。
取 $T$ 的第 $1$ 到第 $2$ 个字符得到字符串 11，它是美丽字符串，因为选择 $i=1$ 并执行操作后，字符串变为 1。
在 $(A,B,C,D)=(0,0,0,1)$ 的情况下，$T$ 的美丽子串如下三种：

• 取 $T$ 的第 $1$ 个字符得到的字符串 1。
• 取 $T$ 的第 $2$ 个字符得到的字符串 1。
• 取 $T$ 的第 $1$ 到第 $2$ 个字符得到的字符串 11。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $N$ 为整数。
• $T$ 是长度为 $N$ 的只包含 0 和 1 的字符串。

由 ChatGPT 4.1 翻译