U506664 无终协语

> “万钧罪责无可赦，再无相聚时。” > > “行于低处如伏兽，听闻号角声。” 不同的语言可以记录同一段历史。 我们可以把语言分为本语与协语，如“果坤”是本语，“大”是协语，“果坤大”“果大坤”“大果坤”都是合法的短语。

使用语言 U 的北原军团和使用语言 T 的萨米部落各自保存了一份古老历史的拷贝。研究发现，语言 T 的句子由两个本语字母组成的“本语”组成，其间（包括一个本语单词两个字母中间）可以插入一些协语字母，而语言 U 中“本语”只占一个字母，没有“协语”，语言 U 的“本语”对应着唯一一个语言 T 的“本语”。 语言 U 的片段 $S_U$ **可以被解读为**语言 T 的片段 $S_T$，当且仅当去除协语字母后，剩下的本语序列有偶数个字母，且该序列与 $S_U$ 恰好对应。 举个例子，如果 U 语言有 `@,#` 两个字母，T 语言有本语字母 `1,2` 与协语字母 `3`，`@` 对应本语 `12`，`#` 对应 `21`，则 T 语言片段 `132132` 只能被解读为 `@@`，`3213` 只能被解读为 `#`。 史书的两份拷贝可以用 U 语言/ T 语言的字符串 $A$ / $B$ 表示，设长度为 $n,m$，两份拷贝的记述顺序不一定相同。某年某一份拷贝被篡改了（篡改不会改变拷贝的长度），现在的 $A$ 与 $B$ 已经不可信。 我们只知道历代历史学者**先后**提出了 $q$ 个解读，第 $i$ 个解读可以表示为 $(k_i,\{x_i\}_1^{k_i},\{y_i\}_1^{k_i})$，设 $x_0=y_0=0,x_{k_i+1}=n,y_{k_i+1}=m$，解读的内容为 $\forall i\in[1,k_i+1]$，有 $B_{[y_{i-1}+1,y_i]}$ 可以被解读为 $A_{[x_{i-1}+1,x_i]}$。 已知史书有不止一个字母，问：从哪个解读开始，这些信息出现了自我矛盾？ 自我矛盾指的是不存在一种 A、B 与字母对应关系的组合，满足所有解读。假设 U 与 T 字母都足够多，不用考虑字母不够用的情况。 ---- ### 形式化题面 对于字符集 $U,T_0,T_1$ 与映射 $f:U\to T_0\times T_0$，$T_0\times T_0$ 为 $T_0$ 中任取两个字符构成的串的集合，**那么**，由 $T=T_0\cup T_1$ 中字符组成的 $S_T$ 可以被解读为由 $U$ 中字符组成的 $S_U$，当且仅当去除 $T_1$ 中字符后，$S_U$ 恰等于 $f(S_T)$，其中 $f(S)$ 为将 $S$ 中所有字符施加变换 $f$ 后顺次连接所得的字符串。 有 $q$ 个约束，每个约束可以表示为 $(k_i,\{x_i\}_1^{k_i},\{y_i\}_1^{k_i})$，设 $x_0=y_0=0,x_{k_i+1}=n,y_{k_i+1}=m$，约束的内容为 $\forall i\in[1,k_i+1]$，有 $B_{[y_{i-1}+1,y_i]}$ 可以被解读为 $A_{[x_{i-1}+1,x_i]}$。问：从哪个约束开始出现矛盾情况？

无

无