#P7487. 【FFT/NTT】三角形[MUTC2013]idiots 改版

【FFT/NTT】三角形[MUTC2013]idiots 改版

【题意】

给定 nn 个长度分别为 aia_i 的木棒,问随机选择 3 个木棒能够拼成三角形的概率。

【输入格式】

第一行 TT,表示数据组数。
接下来若干行描述 TT 组数据,每组数据第一行是 nn,接下来一行有 nn 个数表示 aia_i
T20,3n105,1ai105T≤20,3≤n≤10^5 ,1≤a_i≤10^5

【输出格式】

TT 行,每行一个数,表示这个概率的最简分数表示形式在模 998244353998244353 的意义下的逆元。

2
4
1 3 3 4
4
2 3 3 4
499122177
1