#P12875. PalindromemordnilaP

    ID: 12061 传统题 12000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-双射计数KMP自定义排序规则一维前缀和阈值划分大小情况离线查询扫描中维护贡献根号分块2025“钉耙编程”中国大学生算法设计暑期联赛(10)

PalindromemordnilaP

PalindromemordnilaP

Problem Description

温馨提示:请注意你代码的时间常数。 定义一个字符串 ss 的子串 s[l,r]s_{[l,r]} 为,依次拼接 sl,sl+1,⋯ ,srs_l,s_{l+1},\cdots,s_r 而形成的字符串,其中下标从 11 开始标号。 定义一个字符串 ss 是广义回文的,当且仅当它能被表示为 s=t1+t2+⋯+tks=t_1+t_2+\cdots+t_k,其中 tit_i 为任意非空字符串,kk 为 ≥2\ge2 的正整数,且满足对于任意 1≤i≤k1\le i\le k,ti=tk+1−it_i=t_{k+1-i}。 例如,字符串 abcbacab\texttt{abcbacab} 是广义回文的,因为它可以被表示为 $\texttt{ab}+\texttt{c}+\texttt{ba}+\texttt{c}+\texttt{ab}$。 给定一个长为 nn,只包含前 mm 个小写字母的字符串 ss。你要处理 qq 次查询:

  • 给定 l,rl,r,问 s[l,r]s_{[l,r]} 有多少个子串,满足它是广义回文的。 由于出题人懒得造有强度的数据,因此字符串 ss 随机生成。具体的,每个位置上的字符均在前 mm 个小写字母中等概率随机选取。

Input

本题有多组数据。第一行一个正整数 TT(1≤T≤1031\le T\le10^3)表示数据组数。对于每组测试数据: 第一行输入三个正整数 n,m,qn,m,q(1≤n≤2⋅1051\le n\le2\cdot10^5,1≤m≤261\le m\le26,1≤q≤2⋅1051\le q\le2\cdot10^5)。 第二行输入字符串 ss。 接下来 qq 行,每行两个正整数 l,rl,r(1≤l≤r≤n1\le l\le r\le n)表示一个询问。 保证 ∑n≤2⋅106\sum n\le2\cdot10^6,∑q≤2⋅106\sum q\le2\cdot10^6。

Output

为了减少输出量,对于每组数据,记第 ii 次询问的答案为 ansians_i,输出 ⊕1≤i≤qi⋅ansi\oplus_{1\le i\le q}i\cdot ans_i,其中 ⊕\oplus 表示按位异或。

Sample Input

1
8 3 2
abcbacab
1 8
2 6

Sample Output

12

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(10)