Expected Components

题意翻译

一个长度为 $ n $ 的环状序列 $ \{a_i\} $ ，其中的数值满足 $ 1\leq a_i\leq n $ ，序列中可能有相等的数。 序列 $ \{a_i\} $ 的一个排列和另外一个排列本质相同，当且仅当可以通过旋转使它们变得每一项都对应相等。 对于 $ \{a_i\} $ 的任何一种本质不同排列，可以构造一张 $ n $ 个点的无向图，节点 $ i $ 对应序列中的 $ a_i $ 。若序列中相邻两项相等（首项和末项也相邻），则在它们的对应的节点之间连一条边。这个排列的价值为无向图的连通块数量。 给定序列 $ \{a_i\} $ ，从它的所有本质不同排列中等概率选择一个，求价值的期望。

题目描述

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 $ .

输入输出格式

输入格式

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 $

输出格式

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} $ .

输入输出样例

输入样例 #1

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

输出样例 #1

1
2
3
5
358642921

说明

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 $