← 返回题目列表

AtCoder · abc418_g

G. 二元运算

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

分数: 650 点

问题陈述

有 16 整数元组 (A, B, C, D) 满意 A, B, C, D \in \lbrace 0, 1 \rbrace。对于他们每个人,解决以下问题。

非空字符串 S 组成 0 和 1 满足以下条件时称为漂亮字符串:

  • (条件)您可以执行以下操作序列,直到长度达到 S 变为 分别为 1 并使唯一剩余的字符 S be 1.
    1. 选择任意整数 i 满意 1 \leq i \leq |S| - 1.
    2. 定义一个整数 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.
    3. 删除 S_i 和 S_{i+1},并插入对应的数字 x 代替他们。
      例如,如果 牌匾上写着 S= 10101 然后你选择 i=2,运算后的字符串为 1001 if B=0,和 1101 if 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