#agc055a. [agc055_a]ABC Identity

[agc055_a]ABC Identity

翻译

给定长度为 3n(1n2e5)3n (1 \le n \le 2e5) 的序列,其中字母 ABC 各有 nn 个。

一个合法序列 TT 满足以下条件:

  • 其长度为 3k(1kn)3k (1 \le k \le n)

  • T1=T2=...=TkT_1 = T_2 = ... = T_k

  • Tk+1=Tk+2=...=T2kT_{k + 1} = T_{k + 2} = ... = T_{2k}

  • T2k+1=T2k+2=...=T3kT_{2k + 1} = T_{2k + 2} = ... = T_{3k}

  • T1,Tk+1,T2k+1T_1, T_{k + 1}, T_{2k + 1} 互不相同。

求一个把这个序列分成不多于 66 个合法的序列的方案。

可以证明,一定存在一种合法的划分。