T128880
2026-08-18 20:25:22
发布于：浙江
4阅读
0回复
0点赞
O(nlogn）
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long a[2005];
long long jie[2004];
long long niy(long long _1,long long _2){
if(_2==0) return 1;
long long ctc=niy(_1,_2/2);
if(_2%2==0) return ctc*ctc%mod;
else return ctc*ctc%mod*_1%mod;
}
long long C(long long _1,long long _2){
if(_1<_2||_2<0||_1<0) return 0;
return jie[_1]*niy(jie[_2],mod-2)%mod*niy(jie[_1-_2],mod-2)%mod;
}
void solve(){
int n,k;
cin>>n>>k;
long long cnt=0;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt+=a[i];
}
sort(a+1,a+n+1);
long long bb=(n-2)/(k+1)+2;
long long al=n-bb,c=n/2;
long long ans=0;
for(int i=1;i<=n;i++){
cnt-=a[i];
if(al-c>i-1) continue;
if(n-i+1<c) continue;
ans=ans+a[i]*C(n-i,c-1)%mod*C(i-1,al-c)%mod;
if(n-i==0||n-i==c-1) ans+=cnt%mod*C(i-1,al-c)%mod;
else ans+=cnt%mod*C(n-i-1,c-2)%mod*C(i-1,al-c)%mod;
ans%=mod;
}
cout<<ans*jie[al]%mod*jie[bb]%mod<<endl;
}
int main(){
ios::sync_with_stdio(0);
jie[0]=1;
for(int i=1;i<=2000;i++){
jie[i]=jie[i-1]*i%mod;
}
int t;
cin>>t;
while(t--) solve();
return 0;
}
这里空空如也
有帮助，赞一个