#P11922. [2023年联测]自动机

    ID: 11072 传统题 2000ms 1024MiB 尝试: 18 已通过: 1 难度: 9 上传者: 标签>数据结构贪心字符串CF2600构造数学模拟

[2023年联测]自动机

自动机(automaton)

题目描述

给定正整数 p,qp,q。01 串集合 LL 是按下列规则生成的最小集合:

  • 空串属于 LL。
  • 若 S1,…,Sp+q+1∈LS_1,\ldots,S_{p+q+1}\in L,且 c1,…,cp+q∈{0,1}c_1,\ldots,c_{p+q}\in\{0,1\} 中恰有 pp 个 0 和 qq 个 1,则 S1c1S2c2⋯Sp+qcp+qSp+q+1∈LS_1c_1S_2c_2\cdots S_{p+q}c_{p+q}S_{p+q+1}\in L。

对每个 S∈LS\in L,定义它的“证明”由以下规则生成:

  • 空串的证明是空串。
  • 对上述构造,若 TiT_i 是 SiS_i 的证明,则
1(T10)(T20)⋯(Tp+q0)Tp+q+11(T_1 0)(T_2 0)\cdots(T_{p+q}0)T_{p+q+1}

是 S1c1S2c2⋯Sp+qcp+qSp+q+1S_1c_1S_2c_2\cdots S_{p+q}c_{p+q}S_{p+q+1} 的一个证明。括号和空格只用于解释拼接,不实际出现在字符串中。

给定非空串 S∈LS\in L,构造它的任意一个证明,保证有解。

等价描述

定义 01 串二元组的集合 UU:(S,T)∈U(S,T)\in U 当且仅当二者均为空串,或存在 Si,Ti,ciS_i,T_i,c_i,满足每个 (Si,Ti)∈U(S_i,T_i)\in U,c1,…,cp+qc_1,\ldots,c_{p+q} 中恰有 pp 个 0 和 qq 个 1,并且

S=S1c1S2c2⋯Sp+qcp+qSp+q+1,S=S_1c_1S_2c_2\cdots S_{p+q}c_{p+q}S_{p+q+1}, T=1(T10)(T20)⋯(Tp+q0)Tp+q+1.T=1(T_1 0)(T_2 0)\cdots(T_{p+q}0)T_{p+q+1}.

这样的集合唯一。要求输出任意满足 (S,T)∈U(S,T)\in U 的 TT。

输入格式

第一行三个正整数 n,p,qn,p,q。第二行一个长度为 nn 的 01 串 SS。

输出格式

输出任意一个符合要求的证明串 TT。

输入样例 1

15 2 1
010110000100100

输出样例 1

11000010000100001000

样例解释

记 ε\varepsilon 为空串。(ε,ε)∈U(\varepsilon,\varepsilon)\in 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×107p+q\le n\le2\times10^7,保证存在合法证明。

从下列两组性质中各选一项形成一个子任务,其分值等于两项括号内数字的乘积。严格包含的子任务间有依赖关系。

第一组:

  • n≤5×102n\le5\times10^2(1)。
  • n≤3×103n\le3\times10^3(1)。
  • n≤2×105n\le2\times10^5(1)。
  • n≤2×106n\le2\times10^6(1)。
  • n≤2×107n\le2\times10^7(1)。

第二组:

  • p=q=1p=q=1(2)。
  • p=1,q=2p=1,q=2(1)。
  • p=1,q=3p=1,q=3(2)。
  • p=1,q≥199p=1,q\ge199(4)。
  • p=1p=1(1)。
  • p,qp,q 互素且 p+q≥200p+q\ge200(2)。
  • p,qp,q 互素(2)。
  • p+q≥200p+q\ge200(3)。
  • 无特殊限制(3)。