#P14655. [IATI2014]ABWORDS

    ID: 13871 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-序列构造周期规律验证奇偶性分析2-adic 赋值

[IATI2014]ABWORDS

题目描述

我们把所有满足下列条件的字符串称为“单词”:

  • 只包含大写字母 A 和 B;
  • 长度至少为 2;
  • 首字符必须是 A。

在每个单词上定义两种操作:

操作 R1

只改变最后一个字母:

  • A 变成 B
  • B 变成 A

其余字母保持不变。

操作 R2

设原单词为 w,构造新单词 t:

  • t 的第一个字母一定是 A;
  • 对于 i>1,t_i 由原单词中相邻的 w_{i-1} 和 w_i 决定:
    • 若 w_{i-1} = w_i,则 t_i = B
    • 否则 t_i = A

然后把 w 替换为 t。

若从某个单词 w 出发,按某种顺序连续执行 N 次 R1/R2 操作,满足:

  1. 第 N 次操作后得到的结果再次等于原单词 w;
  2. 中间出现的所有单词两两不同,且都不同于原单词 w;

则称这是 w 的一个 N-transformation。

给定 N > 1,请找出一个长度尽可能短的单词,使它存在 N-transformation;若不存在则输出 NO。

输入格式

输入一个正整数 N (N > 1)。

输出格式

若存在解,输出:

  • 第 1 行:一个长度最短的合法单词;
  • 第 2 行:一个长度为 N 的仅由 1 和 2 组成的字符串,表示依次执行的规则编号(1 表示 R1,2 表示 R2)。从第一行给出的单词开始按顺序执行这些操作后,应当第一次重新得到它自己,且中途不出现重复单词。

若不存在解,则输出一行 NO。

数据范围

  • 2 <= N <= 100000
  • 20% 数据:N <= 30
  • 40% 数据:N <= 200
  • 70% 数据:N <= 10000

样例

输入

6

输出

AABB
221212

样例解释

长度小于 4 的单词都不能作为某个 6-transformation 的起点;而长度为 4 的单词 AABB 可以,其对应变换序列如下:

AABB -> ABAB -> AAAA -> AAAB -> ABBA -> ABBB -> AABB

评分说明

  • 若正确判断“无解”,该测试点得满分;
  • 若输出的第一行不是合法单词,或第二行不是所要求的 N-transformation,则该测试点得 0 分;
  • 否则,得分与第一行单词长度距离最优长度的接近程度有关。