bzoj#P2528. [POI2011] Periodicity

[POI2011] Periodicity

题目描述

给定一个字符串 SS,其长度为 NN,如果对于任意的 ii1int1\leq i\leq n-t)有 Si=Si+tS_i=S_{i+t}1t<n11\leq t < n-1),那么称其满足性质 g(T)g(T)。定义 Per(S)\operatorname{Per}(S) 为所有使得 SS 满足性质 g(T)g(T) 的整数 TT 的集合。

例如:Per(ABIABUABIAB)={6, 9}\operatorname{Per}(\texttt{ABIABUABIAB})=\{6,\ 9\},$\operatorname{Per}(\texttt{01001010010})=\{5,\ 8,\ 10\}$,Per(0000)={1, 2, 3}\operatorname{Per}(\texttt{0000})=\{1,\ 2,\ 3\}。你的任务是构造一个长度恰好为 NN 的 01 串,使得

  • 该串的 Per\operatorname{Per} 集合和 SS 相等。
  • 在所有满足条件 1 的 01 串中,该串的字典序最小。

输入格式

第一行是一个整数 KK,表示这个数据里你要处理 KK 个问题。

接下来 KK 行,每行有一个仅包含大写字母并且长度不超过 200000200000 的字符串。

输出格式

KK 行,第 II 行对应输入的第 ii 个字符串的答案。如果不存在这样的 01 串,输出 XXX

3
ABIABUABIAB
BABBAB
BABURBAB
01001101001
010010
01000010

来源

鸣谢 Object022。