题目如下：

F - Double Chance 题目链接

思路 or 题解：

期望公式：∑val×p\sum val \times p∑val×p
还可以细分：
如果两次抽出的值是相同的，都是 xxx，那么抽出的方案数为 cntx×cntxcnt_x \times cnt_xcntx​×cntx​。
如果两次抽出的值不同，那么抽出的方案数为：cntx×minxcnt_x \times min_xcntx​×minx​
minxmin_xminx​ 指的是小于xxx的个数

综上所述：
抽出最大值为xxx的概率为: cntx2+cntx∗minx∗2m2∗x\frac{cnt_x^2 + cnt_x * min_x * 2}{m^2} * xm2cntx2​+cntx​∗minx​∗2​∗x
其中 mmm 为袋子里的元素个数

时间复杂度: O(n2∗logn2)O(n^2 * logn^2)O(n2∗logn2)

优化：

此处我们将上述公式的 m2m^2m2 中的 mmm 改成输出中的 nnn，方便分数加法，最后乘上 n2m2\frac{n^2}{m^2}m2n2​ 即可

式子变为：
(2cntx−1)+2minxn2×x\frac{(2cnt_x - 1) + 2min_x}{n ^ 2} \times xn2(2cntx​−1)+2minx​​×x

显然 cntcntcnt 和 2cntxn2\frac{2cnt_x}{n^2}n22cntx​​ 都可以用树状数组存，以 xxx 为下标即可。

AC代码：

#define int long long
//#define int long long
#define PII pair
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int MOD = 998244353;
const int N = 400009;
int n;
int ksm(int a, int b, int p)
{a %= p;int ret = 1;while (b){if (b % 2)ret = ret * a % p;a = a * a % p;b /= 2;}return ret;
}
#define getny(x, p) (ksm(x, (p)-2, p))
#define fracny(x, y, p) (((x) % (p)) * getny(y, p) % (p))int cnt[N];int pfn;#define lowbit(x) ((x) & (-(x)))
int c[N]; // cnt
void add(int x, int v)
{for (int i = x; i <= 2e5; i += lowbit(i))c[i] += v;
}
int query(int x)
{int ret = 0;for (int i = x; i; i -= lowbit(i))ret += c[i];return ret;
}
int c1[N]; //((cnt*2)/(n^2))*x
void add1(int x, int v)
{for (int i = x; i <= 2e5; i += lowbit(i))c1[i] += v;
}
int query1(int x)
{int ret = 0;for (int i = x; i; i -= lowbit(i))ret += c1[i];return ret;
}#define gm(x) (((x) % MOD + MOD) % MOD)int ans;void add(int x)
{pfn++;cnt[x]++;add(x, 1);add1(x, fracny(2, n * n, MOD) * x % MOD);ans = (ans + fracny(2 * cnt[x] - 1 + query(x - 1) * 2, n * n, MOD) * x % MOD) % MOD;ans = (ans + gm(query1(2e5) - query1(x))) % MOD;
}void solve()
{buff;cin >> n;for (int i = 1; i <= n; i++){int x;cin >> x, add(x);cout << ans * fracny(n * n, pfn * pfn, MOD) % MOD << '\n';}
}
signed main()
{buff;solve();
}

参考文章
感谢：