Expected Value Again
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 3100
Tags: combinatorics, strings

You are given integers $$$n$$$, $$$k$$$. Let's consider the alphabet consisting of $$$k$$$ different elements.

Let beauty $$$f(s)$$$ of the string $$$s$$$ be the number of indexes $$$i$$$, $$$1\le i<|s|$$$, for which prefix of $$$s$$$ of length $$$i$$$ equals to suffix of $$$s$$$ of length $$$i$$$. For example, beauty of the string $$$abacaba$$$ equals $$$2$$$, as for $$$i = 1, 3$$$ prefix and suffix of length $$$i$$$ are equal.

Consider all words of length $$$n$$$ in the given alphabet. Find the expected value of $$$f(s)^2$$$ of a uniformly chosen at random word. We can show that it can be expressed as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime and $$$Q$$$ isn't divided by $$$10^9 + 7$$$. Output $$$P\cdot Q^{-1} \bmod 10^9 + 7$$$.

Input format:
The first and the only line contains two integers $$$n$$$, $$$k$$$ ($$$1\le n \le 10^5$$$, $$$1\le k\le 10^9$$$) — the length of a string and the size of alphabet respectively.

Output format:
Output a single integer — $$$P\times Q^{-1} \bmod 10^9 + 7$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$9$$$ words of length $$$2$$$ in alphabet of size $$$3$$$ — $$$aa$$$, $$$ab$$$, $$$ac$$$, $$$ba$$$, $$$bb$$$, $$$bc$$$, $$$ca$$$, $$$cb$$$, $$$cc$$$. $$$3$$$ of them have beauty $$$1$$$ and $$$6$$$ of them have beauty $$$0$$$, so the average value is $$$\frac{1}{3}$$$.

In the third example, there is only one such word, and it has beauty $$$99$$$, so the average value is $$$99^2$$$.

Example input:
2 3

Example output:
333333336

Example input:
1 5

Example output:
0

Editorial:
Let $$$ f_i (s) $$$ be a function of the string $$$ s $$$ equal to $$$ 1 $$$ if the prefix and suffix of length $$$ i $$$ are equal, and equal to $$$ 0 $$$ otherwise. We need to calculate $$$ E ((f_1 (s) + f_2 (s) + \dots + f_{n-1}(s))^2) = $$$ (using linearity of expectation) $$$ \sum_{i = 1}^{n-1} E(f_i (s) ^ 2) + \sum_{1 \le i, j \le n-1, i \neq j} E (f_i (s) f_j (s)) $$$.
We will call the number $$$ k $$$ the period of the string $$$ s $$$ if $$$ s [i] = s [i + k] $$$ for all $$$ 1 \le i \le len (s) + 1-k $$$. Moreover, the length of $$$ s $$$ is not required to be divided by $$$ k $$$.
** Statement 1: ** $$$ f_i (s) = 1 \iff $$$ $$$ n-i $$$ is the period of the string is $$$ s $$$.
** Proof: ** that $$$ f_i (s) = 1 $$$ is equivalent to $$$ s[1]s[2] \dots s[i] = s[n + 1-i]s[n + 2 -i] \dots s[n] $$$, which is equivalent to the fact that $$$ s [j] = s [j + n - i] $$$ for $$$ j $$$ from $$$ 1 $$$ to $$$ i $$$.
** Statement 2: ** $$$ E (f_i (s)) = k ^ {- i} $$$.
** Proof: ** The probability that $$$ f_i (s) = 1 $$$ is $$$ k ^ {- i} $$$, since each of the last $$$ i $$$ characters is uniquely determined from the previous ones.
** Statement 3: ** Let $$$ i_1 = n-i, j_1 = n-j $$$. Then $$$ E (f_i (s) f_j (s)) = k ^ {max (i_1 + j_1 - n, gcd (i_1, j_1)) - n} $$$.
** Proof: ** Assume that $$$ f_i (s) = f_j (s) = 1 $$$. We know that the string is $$$ i_1 $$$ and $$$ j_1 $$$-periodic. Consider a graph of $$$ n $$$ string positions, and draw edges between positions at distances $$$ i_1, j_1 $$$. Then the number of different strings satisfying $$$ f_i (s) = f_j (s) = 1 $$$ is $$$ k ^ {comps} $$$, where $$$ comps $$$ is the number of connected components of our graph. Then $$$ E (f_i (s) f_j (s)) = k ^ {comps-n} $$$. Thus, we need to show that $$$ comps = max (i_1 + j_1 - n, gcd (i_1, j_1)) $$$.
The case of $$$ i_1 + j_1 \le n $$$ is obvious: in this case, by subtracting and adding $$$ i_1, j_1 $$$ we can show that the string has period $$$ gcd (i_1, j_1) $$$, in this case $$$ comps = gcd (i_1, j_1 ) $$$. We now consider the case when $$$ i_1 + j_1> n $$$.
Without loss of generality, $$$ i <j \implies i_1> j_1 $$$. We write out in a circle numbers from $$$ 1 $$$ to $$$ i_1 $$$. They denote the components of connectivity when we draw only the edges connecting the positions at a distance of $$$ i_1 $$$. Now we need to add edges of the form $$$ (k, k + j_1) $$$ for $$$ k = 1, 2, \dots, j $$$ (here $$$ i_1 + 1 = 1, \dots $$$). Moreover, we know that $$$ j <i_1 $$$.
We will add these edges one at a time and observe how the connected components change. If we connected two positions that were not connected yet, then we reduced the number of connected components by $$$ 1 $$$. Otherwise, we connected two already connected vertices and formed a cycle. When does a cycle form at all? If we consider all the edges of the form $$$ (k, k + j_1) $$$, then our graph is divided into $$$ gcd (i_1, j_1) $$$ cycles - components, each of which contains all positions giving the same residues when divided by $$$ gcd (i_1, j_1) $$$. Thus, it is necessary to calculate how many of these cycles we form. If $$$ t $$$ cycles are formed, then the number of components will be $$$ i_1 - j + t = i_1 + j_1 - n + t $$$.
How many cycles will we create? Let's see if the cycle consisting of positions giving the remainder $$$ x $$$ when divided by $$$ gcd (i_1, j_1) $$$ closes. It closes only if all its vertices are in $$$ [1, j] $$$. This is equivalent to the fact that among the positions in $$$ [j + 1, i_1] $$$, not a single number gives the remainder of $$$ x $$$ when dividing by $$$ gcd (i_1, j_1) $$$. If $$$ i_1-j = i_1 + j_1 - n \ge gcd (i_1, j_1) $$$, then this cannot happen for any $$$ x $$$, $$$ t = 0 $$$, and $$$ comp = i_1 + j_1 - n = max (i_1 + j_1 - n, gcd (i_1, j_1) $$$. Otherwise, there will be exactly $$$ gcd (i_1, j_1) - (i_1 + j_1-n) $$$, where $$$ comp = i_1 + j_1 - n + gcd (i_1, j_1) - (i_1 + j_1-n) = gcd (i_1, j_1) $$$. Thus, the statement is proved.
Further reasoning is standard. We have shown that $$$ E (f_i (s) f_j (s)) $$$ depends only on $$$ i_1 + j_1 $$$ and $$$ gcd (i_1, j_1) $$$. It remains for $$$ s, gcd $$$ to count the number of pairs $$$ i_1, j_1 $$$ such that $$$ s = i_1 + j_1 $$$, $$$ gcd = gcd (i1, j1) $$$, $$$ 1 \le i_1, j_1 \le n-1 $$$. We will do it as follows: if $$$ s_2 = \frac{s}{gcd} $$$, $$$ i_2 = \frac{i_1}{gcd} $$$, $$$ j_2 = \frac{j_2}{gcd} $$$, then we rewrite it as $$$ s_2 = i_2 + j_2 $$$, $$$ gcd (i_2, j_2) = 1 $$$, $$$ 1 \le i_2, j_2 \le \lfloor \frac{n-1}{gcd} \rfloor $$$. Now we just need to find the number of numbers coprime to $$$ s_2 $$$ on the segment $$$ [max (1, s - \lfloor \frac{n-1}{gcd} \rfloor), min (s-1, \lfloor \frac{n-1}{gcd} \rfloor)] $$$. This can be done for $$$ O (2 ^ {primes}) $$$, where $$$ primes $$$ is the number of prime divisors of $$$ s_2 $$$.
It can be shown that this gives the asymptotics of $$$ O (n\log {n} ^ 2) $$$ (If you have a better one, please share in the comments!)