NZIC 2026 Round 1（新西兰信息学竞赛 2025 第一轮）

D.Repeat Repeat（重复，再重复）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 256 MB 时间限制： 1.0 秒

• problem statement
• submit
• submissions

---

题目描述

鸭子 Pablo 喜欢重复字符串。

具体来说，在休息日里，他会先选取一个长度为：

$$N$$

的初始字符串，然后把它重复：

$$M$$

次，形成字符串：

$$S$$

因此字符串 (S) 的长度为：

$$N\times M$$

例如，Pablo 可能从字符串：

ABBC

开始。

如果将它重复 3 次，就会得到：

ABBCABBCABBC

---

然而，有一天发生了一件悲惨的事情。

Pablo 不小心把他的字符串弄掉了，结果其中一些字符被随机翻转，形成了损坏后的字符串：

$$T$$

Pablo 已经忘记原来的字符串 (S) 是什么了，而且他希望能够把它恢复出来，因此前来向你寻求帮助。

给定：

$$N,\ M,\ T$$

请问：

至少需要替换 (T) 中多少个字符，才能使它变成一个可能的原字符串 (S)？

如果一个字符串可以通过：

将某个长度为 (N) 的字符串重复 (M) 次

得到，那么这个字符串就被认为是一个合理的猜测（plausible guess）。

为了获得额外分数，你还可以输出一个符合条件的字符串 (S)。

---

输入格式

第一行包含两个用空格分隔的整数：

N M

第二行包含字符串：

T

它的长度为：

$$N\times M$$

字符串 (T) 只包含大写英文字母：

A

到：

Z

---

输出格式

第一行输出一个整数：

$$X$$

表示：

至少需要替换多少个字符，才能把 (T) 变成一个合理的字符串 (S)。

---

作为可选内容，为了获得额外分数，你可以在第二行输出一个合理的字符串：

$$S$$

该字符串必须满足：

• 通过替换 (T) 中恰好 (X) 个字符得到；
• 可以由某个长度为 (N) 的字符串重复 (M) 次得到；
• 只包含大写英文字母 A 到 Z。

具体评分方式请参见后面的评分说明。

---

数据范围

$$1\le N\le10^5$$ $$1\le M\le10^5$$ $$1\le N\times M\le10^5$$

字符串 (S) 和 (T) 都只包含大写英文字母：

A-Z

---

子任务

• 子任务 1（10%）：

$$N\times M\le100$$

• 子任务 2（15%）：

$$M=2$$

• 子任务 3（15%）：

$$N=1$$

• 子任务 4（20%）：

字符串 (T) 只包含：

A

或者：

B

这两个大写字母。

• 子任务 5（40%）：

没有额外限制。

---

评分方式

对于任意一个测试点：

• 如果你正确输出了 (X)，但输出的字符串 (S) 不正确，或者根本没有输出字符串 (S)，那么这个测试点可以获得 80% 的分数；
• 如果你正确输出了 (X)，并且还输出了一个合法的字符串 (S)，那么这个测试点可以获得 100% 的分数。

某个子任务的最终得分为：

该子任务的总分 × 你在该子任务所有测试点中得到的最低百分比。

---

样例说明

样例 1

字符串：

ABCFABCDAECD

中，可以替换第 4 个字符和第 10 个字符，得到：

ABCDABCDABCD

这是一个合理的原字符串猜测。

因为我们知道原字符串是：

将一个长度为 4 的字符串重复 3 次得到的。

而：

ABCDABCDABCD

正好可以由：

ABCD

重复 3 次得到。

我们只修改了：

$$2$$

个字符。

并且不可能用更少的修改次数完成。

---

样例 2

这里，原始字符串是：

一个字符重复 5 次得到的字符串。

字符串：

AAAAA

就是一个合理的猜测。

从：

ABCDE

变成：

AAAAA

只需要修改：

$$4$$

个字符。

---

样例输入 1

4 3
ABCFABCDAECD

样例输出 1

2
ABCDABCDABCD

---

样例输入 2

1 5
ABCDE

样例输出 2

4
AAAAA

测试点编号	难度层级	N	M	特殊性质	预期修改次数	设计目的
1	弱数据	1		最小规模，单个字符	0	检查最小边界及基本输出格式
2		3	2	两列出现次数并列	2	检查并列时选择字典序更小的字母
3	正常数据	4	3	原字符串已经由相同基础串重复组成	0	检查无须修改的情况
4		5		包含唯一众数、并列众数和不同错误分布	9	综合检查逐列统计、最优字符选择与修改次数累计
5	压力数据	100		字符串长度 10000，每列目标字符出现 51 次	4900	检查较大规模循环、长字符串输出和 long long 累计逻辑