#B4139. [信息与未来 2016] 字符串替换
[信息与未来 2016] 字符串替换
题目描述
小明最近迷上了字符串操作。对每个字符串,小明每次可以执行以下两种操作之一:
- 把字符串的某个字符改成任意一个其他字符,花费 的代价;
- 交换字符串中的两个字符,花费 的代价。
小明发现,把一个字符串通过一系列的操作,可以转换成任何一个与之等长的字符串。
例如,把 变为 的一种代价为 的操作序列如下:
- (替换 为 ,代价为 )。
- (交换 和 ,代价为 )。
- (替换 为 ,代价为 )。
- (替换 为 ,代价为 )。
小明发现,无法用少于 次的代价将 变为 。
显然,不同的转换方案花费的代价是不同的,请编程帮助小明计算把一个字符串变为另一个字符串的最小代价。
输入格式
一行两个用空格隔开的正整数 (字符串长度),(数据生成器的初始数值)。
本题中的字符串根据给定的初始数值 按以下规则生成:
$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad s_i\leftarrow(s_{i-1}\times345) \bmod 19997 \end{aligned} $$第二个字符串的第 个字符的 ASCII 码为 。
然后令 。
$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad t_i\leftarrow(t_{i-1}\times345) \bmod 19997 \end{aligned} $$第二个字符串的第 个字符的 ASCII 码为 。
输出格式
一行一个非负整数,表示将第一个字符串转换为第二个字符串的最少代价。
4 35
2
100 31
29
提示
。
本题原始满分为 。