← 返回题目列表

AtCoder · awc0105_c

C. 密码转换和纠正

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

Takahashi 正在尝试加密消息 S 由小写英文字母组成,带长度 N.

在加密中,每个字符都被视为其 ASCII 代码(整数值)。小写英文字母的 ASCII 码为 97 为 a, 98 为 b, …, 122 为 z.

首先,他选择一个整数 k (1 \le k < N)并将消息拆分为 上半场 由第一个组成 k 字符和 下半场 由剩余的 N - k 字符。

让 X_L 为前半部分所有字符的 ASCII 码的按位异或 (XOR),并且 X_R 为后半部分所有字符的ASCII码异或。即如果前半部分字符的ASCII码为 s_1, s_2, \ldots, s_k,那么 X_L = s_1 \oplus s_2 \oplus \cdots \oplus s_k,下半场也是如此。在这里, \oplus 表示按位异或。

拆分后,进行以下变换:

  • 替换ASCII码 c 每个字符的前半部分带有 c \oplus X_R.
  • 替换ASCII码 c 后半部分的每个字符 c \oplus X_L.

让 A_1, A_2, \ldots, A_N 是 N 转换后获得的整数值,按顺序排列。请注意,每个 A_i 是介于 0 和 127 包括在内,但不一定属于小写英文字母的 ASCII 码范围(97 to 122 包括)。

因此,高桥选择了 修正顺序 D_1, D_2, \ldots, D_N,并且对于每个 i (1 \le i \le N),最终的密码值为 A_i + D_i。为了使密文有效,所有最终值必须落在小写英文字母的 ASCII 代码范围内。

修正顺序 D 必须满足以下所有条件:

  • 每个 D_i 是一个非负整数。
  • D_1 \ge D_2 \ge \cdots \ge D_N (单调非增)。
  • 对于所有人 i (1 \le i \le N), 97 \le A_i + D_i \le 122 满意。

对于分割位置 k,如果存在校正序列 D 满足上述所有条件,则 k 被称为 良好的分割位置.

查找良好分割位置的数量。

约束

  • 2 \leq N \leq 5000
  • S 是一串小写英文字母,长度为 N

输入

N
S
  • 第一行包含一个整数 N 代表消息的长度。
  • 第二行包含一个字符串 S 小写英文字母及长度 N.

输出

以整数形式输出良好分割位置的数量。


示例输入 1

4
abcd

示例输出 1

3

示例输入 2

3
aaa

示例输出 2

1

示例输入 3

30
abcdefghijklmnopqrstuvwxyzabcd

示例输出 3

1

示例输入 4

100
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuv

示例输出 4

4

示例输入 5

2
az

示例输出 5

1