赛时感觉要分讨，发现不可能写完了，于是决定记一下分讨结果。

感觉也可能是造自动机，赛后看题解吧。

这场 F 不会的时候先去写 G 了，发现 G 没时间写完了突然又会 F 了。

竞速赛，40 min 打完罚坐一个小时。

排名 300+ 但是赛前点了 unrated。

原题链接

称一个由 和 构成的字符串 是好的，当且仅当其可以经过以下任意次操作后得到 。

(操作) 选择下标 ，若 为：

• ，则替换为 ；
• ，则替换为 ；
• ，则替换为 ；
• ，则替换为 。

这里 。

给定字符串 ，求其所有子串中：

• 最长的好的子串的长度（若没有，输出 ）；
• 好的子串的数量；

对每一种 的取值给出答案（共 种），第 行输出使式子 成立的取值所对应的答案。

• 。

---

Algo 1

分类讨论。

0000

• 显然只有字符串 是好的。

0001

• 显然只有全 的串是好的，即形如 。

0010

• 首先，显然字符串的首位必须为 ；

• 其次，若字符串开头的极长全 段的长度为 ，则去除开头的极长全 段后，字符串必须包含 。

  换句话说，我们只需要形如 的字符串，除了 。

0011

• 显然只要字符串的开头为 即可，即形如 。

0100

• 将字符串翻转，然后可以应用 一节的结论；

  即，需要形如 的字符串，除了 。

0101

• 将字符串翻转，然后应用 一节的结论；

  即，需要形如 的字符串。

0110

• 显然操作为异或，因此只需要字符串中 的数量为奇数即可。

0111

• 任何含有 的字符串满足要求。

1000

• 通过暴力枚举可以得到一个表：

  表中的字符串的最终状态是唯一的，其余未列出的字符串最终可以转移到 或 。

  对于较短的字符串可以暴力枚举证明（例如， 位及以内），而更多位的字符串总可以被分成不短于 的两段，故可以归纳证明。

1001

• 注意到 的数量的奇偶性不变，因此 的数量为偶数的字符串均符合要求。

1010

• 暴力枚举打表

  其余字符串可以转移到 或 中任何一个。

1011

• 只有首位为 且其余位均为 的字符串不符合要求。

1100

• 暴力打表发现

  其余字符串可以转移到 或 中任何一个。

1101

• 的翻转版

  只有末位为 且其余位均为 的字符串不符合要求。

1110

• 暴力打表

  其余字符串可以转移到 或 中任何一个。

1111

• 显然任意字符串均可以转移到 。