题意

给你一个形如"SS"的串S，以及一个函数(f(x))，(x)是一个形如"SS"的字符串，(f(x))也是一个形如"SS"的字符串。
(x)是(f(x))的一个前缀，并且要让(f(x))尽量短。

问在(f^{10^{100}}(S))中，[L,R]中所有字符的出现次数。

[字符集为小写字母，|S|<=100000,1<=L<=R<=1e18 ]

解法

可以发现的是S只用考虑前一半，因为进行了许多次变换，已经后一半不在1e18的范围内。

首先我们第一步应该做的是去观察这个函数的变化规律。

通过最初几步的打表，
我们可以发现，设T是S的border，那么f(S)=ST

S->ST->STS->STSST->....

到这里已经相当明显。
这个变化呈现的是一个类似于斐波那契数列的变换。

所以我们可以模拟这个过程。

由于通过斐波那契的变换只需log(1e18)次就可以超过1e18的长度，
时间复杂度是(O(log^2))的。

border的求法相当简单，
我们给串做一次KMP，然后Brd=n-Fail[n]