自动机(automaton)
题目描述
给定正整数 p,q。01 串集合 L 是按下列规则生成的最小集合:
- 空串属于 L。
- 若 S1,…,Sp+q+1∈L,且 c1,…,cp+q∈{0,1} 中恰有 p 个
0 和 q 个 1,则 S1c1S2c2⋯Sp+qcp+qSp+q+1∈L。
对每个 S∈L,定义它的“证明”由以下规则生成:
- 空串的证明是空串。
- 对上述构造,若 Ti 是 Si 的证明,则
1(T10)(T20)⋯(Tp+q0)Tp+q+1
是 S1c1S2c2⋯Sp+qcp+qSp+q+1 的一个证明。括号和空格只用于解释拼接,不实际出现在字符串中。
给定非空串 S∈L,构造它的任意一个证明,保证有解。
等价描述
定义 01 串二元组的集合 U:(S,T)∈U 当且仅当二者均为空串,或存在 Si,Ti,ci,满足每个 (Si,Ti)∈U,c1,…,cp+q 中恰有 p 个 0 和 q 个 1,并且
S=S1c1S2c2⋯Sp+qcp+qSp+q+1,
T=1(T10)(T20)⋯(Tp+q0)Tp+q+1.
这样的集合唯一。要求输出任意满足 (S,T)∈U 的 T。
输入格式
第一行三个正整数 n,p,q。第二行一个长度为 n 的 01 串 S。
输出格式
输出任意一个符合要求的证明串 T。
输入样例 1
15 2 1
010110000100100
输出样例 1
11000010000100001000
样例解释
记 ε 为空串。(ε,ε)∈U,且 010 和 100 都可由三个空子串及两个 0、一个 1 构造,因此它们均有证明 1000。
将原串分解为 (010)1(100)0(010)0(100),分别使用上述证明,得到 1(1000)0(1000)0(1000)0(1000),去掉括号即为样例输出。
数据范围
所有数据满足 p+q≤n≤2×107,保证存在合法证明。
从下列两组性质中各选一项形成一个子任务,其分值等于两项括号内数字的乘积。严格包含的子任务间有依赖关系。
第一组:
- n≤5×102(1)。
- n≤3×103(1)。
- n≤2×105(1)。
- n≤2×106(1)。
- n≤2×107(1)。
第二组:
- p=q=1(2)。
- p=1,q=2(1)。
- p=1,q=3(2)。
- p=1,q≥199(4)。
- p=1(1)。
- p,q 互素且 p+q≥200(2)。
- p,q 互素(2)。
- p+q≥200(3)。
- 无特殊限制(3)。