#P4606. [Apio2008]DNA

    ID: 1363 传统题 1000ms 128MiB 尝试: 150 已通过: 80 难度: 6 上传者: 标签>难度分类提高动态规划线性 DP计数 DP构造与建模序列构造CF2000鸣谢Yts1999上传

[Apio2008]DNA

[APIO2008] DNA

题目描述

DNA 单链由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶组成,分别用大写字母 A、C、G、T 表示。一条 DNA 单链可以写成由这四种字母组成的序列。

字母 N 表示未知的核苷酸,可以独立替换为四种字母中的任意一种。原序列称为待补全序列,替换后得到与之匹配的完整序列。例如 ACCCT 与 ACNNT 匹配,AGGAT 与它不匹配。

以 A、C、G、T 为从小到大的顺序,定义下列范式。

  • 一个序列属于范式 11,当且仅当每个字母都不大于它右侧紧邻的字母。例如 AACCGT 属于范式 11,AACGTC 不属于。
  • 对 j>1j>1,一个序列如果属于范式 j−1j-1,或者可以由一个范式 j−1j-1 的序列接上一个范式 11 的序列得到,则它属于范式 jj。例如 AACCC、ACACC 和 ACACA 都属于范式 33,GCACAC 和 ACACACA 不属于。

长度为 55 的范式 33 序列中,字典序最小的是 AAAAA,最大的是 TTTTT。给定待补全序列 ACANNCNNG,与它匹配的前七个范式 33 序列为:

ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

给定一个长度为 MM 的待补全序列,求与之匹配的所有范式 KK 完整序列中字典序第 RR 小的一个。

输入格式

第一行三个整数 M,K,RM,K,R。第二行一个长度为 MM 的字符串,由 A、C、G、T、N 组成。

输出格式

输出一行,表示要求的完整序列。

9 3 5 
ACANNCNNG
ACAAACCCG
5 4 10 
ACANN
ACAGC

数据范围

1≤M≤500001\le M\le50000,1≤K≤101\le K\le10,1≤R≤2×10121\le R\le2\times10^{12}。保证匹配的范式 KK 完整序列至少有 RR 个,至多有 4×10184\times10^{18} 个。计数可用有符号 64 位整数表示。

原赛中,M≤10M\le10 的测试占 2020 分。每个测试点按输出是否正确给满分或零分。