#P3067. Hyperdrome

    ID: 2200 传统题 1000ms 512MiB 尝试: 380 已通过: 58 难度: 5 上传者: 标签>难度分类普及+/提高-构造与建模奇偶性分析枚举与搜索状态编码位运算异或前缀和数据结构哈希表随机化与近似随机哈希CF1700

Hyperdrome

Hyperdrome

题目背景

来自银河系各地的侏儒参加 Hypergnome 星球上的运动会。其中最受欢迎的项目是 Hyperdrome。

题目描述

裁判给出一个字符串 SS,所有选手要尽快数出其中的 Hyperdrome 子串。若一个子串中的字符可以重新排列成回文串,这个子串就是 Hyperdrome。

子串由 SS 中第 ii 到第 jj 个字符构成,包含两端,满足 1≤i≤j≤N1\le i\le j\le N。按起点和终点计数,即使内容相同,只要位置不同就分别计数。

长度为 ℓ\ell 的字符串 s1s2⋯sℓs_1s_2\cdots s_\ell 是回文串,当且仅当每个位置 ii 都满足 si=sℓ−i+1s_i=s_{\ell-i+1}。

侏儒使用英文大写和小写字母。大小写字母视为不同字符。请帮助选手求出 Hyperdrome 子串的数量。

输入格式

第一行包含一个整数 NN(1≤N≤3×1051\le N\le 3\times10^5),表示字符串长度。第二行是长度为 NN 的字符串 SS。

输出格式

输出一行一个整数,表示 Hyperdrome 子串的数量。

样例

3
aaa
6
7
abadaba
12
3
aAA
5

样例说明

  • 第一组有 66 个符合条件的子串,区间分别为 (1,1)(1,1)、(1,2)(1,2)、(1,3)(1,3)、(2,2)(2,2)、(2,3)(2,3)、(3,3)(3,3)。
  • 第二组有 1212 个符合条件的子串,包括 77 个单字符子串,以及区间 (1,3)(1,3)、(3,5)(3,5)、(5,7)(5,7)、(2,6)(2,6)、(1,7)(1,7)。
  • 第三组的区间是 (1,1)(1,1)、(1,3)(1,3)、(2,2)(2,2)、(2,3)(2,3)、(3,3)(3,3)。区间 (1,3)(1,3) 中的 aAA 可以重排为回文串 AaA。

NEERC 原题 PDF,第 9 页