Expected Components
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 2900
Tags: combinatorics, math, number theory, probabilities

Given a cyclic array $$$a$$$ of size $$$n$$$, where $$$a_i$$$ is the value of $$$a$$$ in the $$$i$$$-th position, there may be repeated values. Let us define that a permutation of $$$a$$$ is equal to another permutation of $$$a$$$ if and only if their values are the same for each position $$$i$$$ or we can transform them to each other by performing some cyclic rotation. Let us define for a cyclic array $$$b$$$ its number of components as the number of connected components in a graph, where the vertices are the positions of $$$b$$$ and we add an edge between each pair of adjacent positions of $$$b$$$ with equal values (note that in a cyclic array the first and last position are also adjacents).

Find the expected value of components of a permutation of $$$a$$$ if we select it equiprobably over the set of all the different permutations of $$$a$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of the cyclic array $$$a$$$.

The second line of each test case contains $$$n$$$ integers, the $$$i$$$-th of them is the value $$$a_i$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

It is guaranteed that the total number of different permutations of $$$a$$$ is not divisible by $$$M$$$

Output format:
For each test case print a single integer — the expected value of components of a permutation of $$$a$$$ if we select it equiprobably over the set of all the different permutations of $$$a$$$ modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

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

Note:
In the first test case there is only $$$1$$$ different permutation of $$$a$$$:

- $$$[1, 1, 1, 1]$$$ has $$$1$$$ component.
- Therefore the expected value of components is $$$\frac{1}{1} = 1$$$

In the second test case there are $$$4$$$ ways to permute the cyclic array $$$a$$$, but there is only $$$1$$$ different permutation of $$$a$$$:

- $$$[1, 1, 1, 2]$$$, $$$[1, 1, 2, 1]$$$, $$$[1, 2, 1, 1]$$$ and $$$[2, 1, 1, 1]$$$ are the same permutation and have $$$2$$$ components.
- Therefore the expected value of components is $$$\frac{2}{1} = 2$$$

In the third test case there are $$$6$$$ ways to permute the cyclic array $$$a$$$, but there are only $$$2$$$ different permutations of $$$a$$$:

- $$$[1, 1, 2, 2]$$$, $$$[2, 1, 1, 2]$$$, $$$[2, 2, 1, 1]$$$ and $$$[1, 2, 2, 1]$$$ are the same permutation and have $$$2$$$ components.
- $$$[1, 2, 1, 2]$$$ and $$$[2, 1, 2, 1]$$$ are the same permutation and have $$$4$$$ components.
- Therefore the expected value of components is $$$\frac{2+4}{2} = \frac{6}{2} = 3$$$

In the fourth test case there are $$$120$$$ ways to permute the cyclic array $$$a$$$, but there are only $$$24$$$ different permutations of $$$a$$$:

- Any permutation of $$$a$$$ has $$$5$$$ components.
- Therefore the expected value of components is $$$\frac{24\cdot 5}{24} = \frac{120}{24} = 5$$$

Example input:
5
4
1 1 1 1
4
1 1 2 1
4
1 2 1 2
5
4 3 2 5 1
12
1 3 2 3 2 1 3 3 1 3 3 2

Example output:
1
2
3
5
358642921

Editorial:
The problem can be solved by applying Burnside's lemma.
$$${"number~of~different~permutations~of~the~cyclic~array~a"} = \frac{"sum~of~number~of~fixed~points~for~each~permutation~function"}{"number~of~permutations~functions"}$$$
Let's focus on two parts.
First part (find the number of different permutations of $$$a$$$):
Let's define a permutation function $$$F_x(arr)$$$ as the function that cyclically shifts the array $$$arr$$$ by $$$x$$$ positions.
In this problem for an array of size $$$n$$$ we have $$$n$$$ possible permutations functions and we would need to find the sum of the number of fixed points for each permutation function.
To find the number of fixed points for a permutation function $$$F_x()$$$ we have that $$$arr_i$$$ must be equal to $$$arr_{(i+x)\%n}$$$, if we add an edge $$$(i,(i+x)\%n)$$$ for each position $$$i$$$ then by number theory we would obtain that $$$gcd(n,x)$$$ cycles would be formed and each one of size $$$\frac{n}{gcd(n,x)}$$$, then we can note that each position $$$i$$$ will belong to the $$$(i\%gcd(n,x))$$$-th cycle, so we can say that the problem can be transformed into counting the number of permutations with repetition in an array of size $$$gcd(n,x)$$$.
Let us denote $$$cnt[v]$$$ as the number of values equal to $$$v$$$ in array $$$a$$$, when we are processing the function $$$F_x()$$$ and we reduce the problem to an array of size $$$gcd(n,x)$$$ we should also decrease $$$cnt[v]$$$ to $$$\frac{cnt[v]}{n/gcd(n,x)}$$$ since each component is made up of $$$\frac{n}{gcd(n,x)}$$$ values, also we must observe that for solving a problem for an array of size $$$x$$$, then $$$\frac{n}{x}$$$ should be a divisor of $$$gcd(cnt[1],cnt[2],\ldots,cnt[n])$$$.
Let us denote $$$cnt_x[v] = \frac{cnt[v]}{n/gcd(n,x)}$$$
So to count the number of permutations with repetition for $$$F_x()$$$ that can be formed with the frequency array $$$cnt_x$$$ we can use the formula $$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$$$
Let us denote $$$G_{all} = gcd(cnt[1],cnt[2],\ldots,cnt[n])$$$
Let us denote $$$fdiv(val)$$$ as the number of divisors of $$$val$$$.
Let us denote $$$tot_{sz}$$$ as the number of permutations with repetition for an array of size $$$sz$$$, from what has been said before we have that $$$\frac{n}{sz}$$$ must be divisible by $$$G_{all}$$$ so we only need to calculate the permutations with repetition for $$$fdiv(G_{all})$$$ arrays.
Now suppose that the number of different values of array $$$a$$$ is $$$k$$$ then $$$G_{all}$$$ must be at most $$$\frac{n}{k}$$$ because the gcd of several numbers is always less than or equal to the smallest of them.
Now to calculate the permutations with repetition for a $$$cnt_x$$$ we do it in $$$O(k)$$$, for that we need to precalculate some factorials and modular inverses before, and since we need to calculate them $$$fdiv(G_{all})$$$ times, then we have that in total the complexity would be $$$O(fdiv(G_{all})\cdot k)$$$ but since $$$G_{all}$$$ is at most $$$\frac{n}{k}$$$ and $$$fdiv(\frac{n}{k})$$$ is at most $$$\frac{n}{k}$$$, substituting it would be $$$O(\frac{n}{k}\cdot k)$$$ equal to $$$O(n)$$$
So to find the sum of the number of fixed points we need the sum of $$$tot_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divides to $$$G_{all}$$$, at the end of all we divide the sum of the number of fixed points by $$$n$$$ and we would obtain the number of different permutations of $$$a$$$.
To find the $$$gcd(n,x)$$$ for $$$1 \le x \le n$$$ we do it with the Euclid's algorithm in complexity $$$O(n\cdot log)$$$ so in total the complexity is $$$O(n\cdot log)$$$
Second part (find the expected value of components of different permutations of $$$a$$$):
Here we will use the Linear Expectation property and we will focus on calculating the contribution of each component separately, the first thing is to realize that the number of components is equal to the number of different adjacent values, so we only need to focus on two adjacent values, except if it is a single component, this would be a special case. If we have $$$k$$$ different values we can use each different pair of them that in total would be $$$k\cdot(k-1)$$$ pairs, we can realize that when we put a pair its contribution would be equal to the number of ways to permute the remaining values, which if we are in an array of size $$$\frac{n}{x}$$$ and we use the values $$$val_1$$$ and $$$val_2$$$ it would be equal to:
$$$tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot cnt_x[val_1] \cdot cnt_x[val_2]$$$
because we removing a value $$$val_1$$$ and another value $$$val_2$$$ from the set, so if we have the formula:
$$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$$$
and $$$val_1$$$ and $$$val_2$$$ are the first two elements then it would be:
$$$\frac{(n-2)!}{(x_1-1)! \cdot (x_2-1)! \cdot \ldots \cdot x_n!}$$$
which would be equivalent to:
$$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!} \cdot \frac{1}{n \cdot (n-1)} \cdot x_1 \cdot x_2$$$
Now to calculate the contribution of the $$$k\cdot(k-1)$$$ pairs we can realize that taking common factor $$$tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)}$$$ in the previous expression it only remains to find the sum of $$$cnt_x[i]\cdot cnt_x[j]$$$ for all $$$i \neq j$$$, this can be found in $$$O(k)$$$ easily by keeping the prefix sum and doing some multiplication. Then at the end we multiply by $$$n$$$ since there are $$$n$$$ possible pairs of adjacent elements in the general array.
Let us define $$$sum_{sz}$$$ as the contribution of components of the permutations with repetition for an array of size $$$sz$$$, then:
$$$sum_{n/x} = tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot (sum~of~(cnt_x[i]\cdot cnt_x[j])~for~i \neq j) \cdot n$$$
Now for each possible permutation with repetition we have by the Burnside's lemma that in the end we divide it by $$$n$$$, so we should also divide by $$$n$$$ the contribution of each component.
Let's define $$$tot'_x = \frac{tot_x}{n}$$$ and $$$sum'_x = \frac{sum_x}{n}$$$
Let's define $$$tot_{all}$$$ as the sum of $$$tot'_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divide to $$$G_{all}$$$.
Let's define $$$sum_{all}$$$ as the sum of $$$sum'_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divide to $$$G_{all}$$$.
The final answer would be:
$$$res = \frac{sum_{all}}{tot_{all}}$$$
The final complexity then is $$$O(n\cdot log)$$$