分数: 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