信友队有质量很高的题目
嗯嗯嗯，大概是场上没做出来，感觉这题出得挺好的。
description
定义 \(\text{rev}(A)\) 为字符串 \(A\) 翻转后得到的字符串，\(+\) 为字符串拼接操作。
现在给你一个字符串 \(s\) 与一个常数 \(k\)，问你有多少个位置不同的子串 \(t\) 满足：
- \(t = A + \text{rev}(A) + A + \text{rev}(A) + ...\)，后一共有 \(k\) 项 \(A\) 或 \(\text{rev}(A)\) 交替。
solution
首先 \(k = 1\) 肯定就是所有子串，\(k = 2\) 就是所有偶回文串的情况（用哈希做）。
然后我们考虑 \(k = 3\) 怎么做。
本质上就是两个回文串交在一起，假设对于一个回文中心 \((i, i + 1)\)，我们令 \(i\) 侧拓展距离为 \(f_i\)，\(i + 1\) 侧拓展距离为 \(g_{i + 1}\)，则对于 \(k = 3\) 时三个串中第二个串的位置的 \([l, r]\)，则满足 \(r - l + 1 <= \min ( f_{r}, g_{l} )\)，我们将 \(\min\) 拆开，发现将有关 \(l, r\) 的项放在两边，发现变成了一个二维数点问题，用 BIT 简单维护一下即可。
现在问题就是 \(k > 3\) 怎么做。
我们其实只需要管中间的两个分界点即可，如果长度合适，我们可以通过回文性质不断翻折得到原子串，具体来说，相当于给 \(f_i, g_i\) 乘上了一个系数做二维数点，而此时我们仅仅只关心中间的两项，通过这个系数，能够确保我们能够将原子串翻折出来，具体来说：
- 当 \(k\) 为奇数，\(f_i = \frac{f_i}{\frac{k}{2}}, g_i = \frac{g_i}{\frac{k}{2}}\)。
- 当 \(k\) 为偶数，\(f_i = \frac{f_i}{\frac{k}{2} - 1}, g_i = \frac{g_i}{\frac{k}{2}}\)。
然后继续去做二维数点。