линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель

g = gcd(a, b)
a = xg
b = yg
pa + qb = pxg + qyg = (px + qy)g

Assume $$$0$$$-based indexing. Let $$$dp_i$$$ denote the degree of the $$$i$$$-th prefix. The length of the prefix, $$$len = i + 1$$$. Firstly, $$$dp_0 = 1$$$, since a $$$1$$$-length string is a palindrome.

Now, to compute $$$dp_i$$$, firstly check to see if $$$i$$$-th prefix is a palindrome or not. If it is not a palindrome $$$dp_i = 0$$$. Otherwise if the prefix is palindrome, its degree would be = (degree of the first half + 1). So, $$$dp_i = dp_{\lfloor\frac{i-1}{2}\rfloor} + 1$$$.

To check whehter the prefix of length $$$len$$$ is a palindrome, you have to check whether the substring on the first $$$\lfloor{\frac{len}{2}}\rfloor$$$ characters is the same as the reverse of the substring on the last $$$\lfloor{\frac{len}{2}}\rfloor$$$ characters. To compare substrings, you can use string hashing. One ways is to build prefix hashes on the string and its reverse to obtain hash of any substring in a O(1) time as described in this blog.

The answer is simply $$$\sum\limits_{i = 0}^{n-1} dp_i$$$.

Code