#B4139. [信息与未来 2016] 字符串替换

[信息与未来 2016] 字符串替换

题目描述

小明最近迷上了字符串操作。对每个字符串,小明每次可以执行以下两种操作之一:

  1. 把字符串的某个字符改成任意一个其他字符,花费 11 的代价;
  2. 交换字符串中的两个字符,花费 00 的代价。

小明发现,把一个字符串通过一系列的操作,可以转换成任何一个与之等长的字符串。

例如,把 hello\tt hello 变为 world\tt world 的一种代价为 33 的操作序列如下: \gdef\ar{\rightarrow}

  1. hello\arwello\tt \red hello \ar \red wello(替换 h\tt hw\tt w,代价为 11)。
  2. wello\arwolle\tt w\blue ell\blue o\ar w\blue oll\blue e(交换 e\tt eo\tt o,代价为 00)。
  3. wolle\arworle\tt wo\red lle \ar wo\red rle(替换 l\tt lr\tt r,代价为 11)。
  4. worle\arworld\tt worl\red e \ar worl\red d(替换 e\tt ed\tt d,代价为 11)。

小明发现,无法用少于 33 次的代价将 hello\tt hello 变为 world\tt world

显然,不同的转换方案花费的代价是不同的,请编程帮助小明计算把一个字符串变为另一个字符串的最小代价。

输入格式

一行两个用空格隔开的正整数 nn(字符串长度),s0s_0(数据生成器的初始数值)。

本题中的字符串根据给定的初始数值 s0s_0 按以下规则生成:

$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad s_i\leftarrow(s_{i-1}\times345) \bmod 19997 \end{aligned} $$

第二个字符串的第 i[1,n]i\in [1,n] 个字符的 ASCII 码为 97+(simod26)97+(s_i \bmod 26)

然后令 t0=snt_0=s_n

$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad t_i\leftarrow(t_{i-1}\times345) \bmod 19997 \end{aligned} $$

第二个字符串的第 i[1,n]i\in [1,n] 个字符的 ASCII 码为 97+(timod26)97+(t_i \bmod 26)

输出格式

一行一个非负整数,表示将第一个字符串转换为第二个字符串的最少代价。

4 35
2
100 31
29

提示

1n106,1s0199971\le n\le 10^6,1\le s_0\le 19997

本题原始满分为 20pts20\text{pts}