[ARC077F] SS
模拟赛题。
首先考虑一次 \(f\) 发生的变化，贪心考虑是选取原串 \(<\frac{len}{2}\) 的最长 border，然后将原串去掉后面的 border 再复制一遍，例如 \(abaaba \to abaab \to abaababaab\)，不难发现这样做是最短的，因为选取了最长 border。
然后考虑对原串的变化，给了这个偶串的性质就要用上，只考虑原串的一半，由于每次是去掉后面的border再复制，长度即为 \(n-|fail_n|\)，其中 \(fail\) 是 kmp 的失配数组，而这个形式又是经典结论最短周期串，于是每次 \(f\) 实际上就是将原串的最短周期串拼到它后面，也就是 \(SS \to STST\) 的形式。
然后发现串长增长很快，是一个斐波那契长度，于是暴力处理出来所有串查询即可。
auto cal = [&](i64 x) -> array <i64, 26> {
int i = now;
array <i64, 26> ans = {};
while (x > n) {
while (i >= 0 && f[i] > x) i--;
assert(i >= 0);
x -= f[i];
for (int j = 0; j < 26; j++) ans[j] += g[i][j];
}
for (int j = 0; j < x; j++) ans[s[j] - 'a']++;
return ans;
};