GYM106259F

GYM106259F先排序 这样不用取绝对值每一场的概率是一样的 一共n*(n-1)/2场 选择n-1 场 每场的贡献就是2/n(a[i]-a[i-1])可以前缀和求也可以考虑贡献这里讲解贡献法对于i到j 如果选择a[j]-a[i] 我们可以看作a[j]-a[j-1]a[j-1]-a[j-2].......a[i1]-a[i] 如果这么看的话 就是一条链子一样 对于一个相邻节点a[i]-a[i-1] 左边从i左边选任意一个点与i配对 他们之间构成的链都包含了a[i]-a[i-1] 右侧选择任意一个点与i-1 配对 每一种配对形成的链都有a[i]-a[i-1]这一项 那么一共就有(i-1)*(n-i1) 种选择中有这条链 对每一相邻差值计算贡献即可最后乘法逆元计算2/n即可代码实现如下#include bits/stdc.h using namespace std; const int N3e55,mod998244353; #define int long long int a[N]; int qpow(int a,int b){ long long ans1; for(;b;b1){ if(b1){ ans(1LL*ans*a)%mod; } a(1LL*a*a)%mod; } return ans; } void solve(){ int n; cinn; for(int i1;in;i)cina[i]; sort(a1,a1n); long long ans0; for(int i2;in;i){ ans(ans(a[i]-a[i-1])*(i-1)%mod*(n-i1)%mod)%mod; } ans(2LL*ans%mod*qpow(n,mod-2))%mod; coutans\n; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while(t--)solve(); return 0; }