首先考虑本题的$O(n^2)$做法。
$Part1$
对原序列从大到小排序后，考虑每个数字对最终答案的贡献，有第x个数字对答案的贡献十分难以计算，所以考虑计算数字x是集合第K大的方案数，作为数字x对$ans(K)$的贡献，然后对$ans$求前缀和，这样得到了x是集合第1~K大的对答案的贡献
$Part2$
考虑计算$ans(K)$只考虑子集合之中第K大的数的贡献，显然有
$$ ans(k) = sum_{i=k}^n {C_{i-1}^{k-1}*2^{n-i}*a(i)} $$
( $a(i)$表示排序后的原序列 )
显然是一个卷积的形式。
$$ ans(k)*(k-1)! = sum_{i=k}^n{frac{1}{(i-k)!} * 2^{n-i}*a(i)*(i-1)! } $$
$A0(i) = 2^{n-i}*a(i)*(i-1)!$
$A(i) = A0(n-i)$
$B(i) = frac{1}{i!} $
$C0(i) = ans(k)*(k-1)!*$
$C(i) = C0(n-i)$
有
$$ C(k) = sum_{i=0}^{k}{A(i)*B(k-i)} $$
多项式乘法形式，用NTT或者FFT实现O(nlogn)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 #define mod0 998244353 7 #define gn 3 8 #define N 400010 9 #define LL long long 10 11 using namespace std; 12 13 inline int mul(int a,int b,int P){ 14 if(a*(LL)b<(LL)P) return a*b; 15 return (int)(a*(LL)b%(LL)P); 16 } 17 18 inline int add(int a,int b,int P){ 19 if(a+b>=P) return a+b-P; 20 return a+b; 21 } 22 23 inline int qpow(int x,int n,int P){ 24 int ans=1; 25 for(;n;n>>=1,x=mul(x,x,P)) 26 if(n&1) ans=mul(ans,x,P); 27 return ans; 28 } 29 30 int wt[N],R[N]; 31 32 void fnt(int *x,int n,int t,int P){ 33 for(int i=0;i<n;i++) if(i<R[i]) swap(x[i],x[R[i]]); 34 for(int m=1;m<n;m<<=1){ 35 int wn=qpow(gn,(P-1)/(m<<1),P); 36 if(t==-1) wn=qpow(wn,P-2,P); 37 wt[0]=1; 38 for(int i=1;i<m;i++) wt[i]=mul(wt[i-1],wn,P); 39 for(int k=0;k<n;k+=(m<<1)) 40 for(int i=0;i<m;i++){ 41 int &A=x[i+m+k]; 42 int &B=x[i+k],t=mul(A,wt[i],P); 43 A=add(B,P-t,P); B=add(B,t,P); 44 } 45 } 46 if(t==-1){ 47 int tmp=qpow(n,P-2,P); 48 for(int i=0;i<n;i++) x[i]=mul(x[i],tmp,P); 49 } 50 } 51 52 int n,m; 53 int a[N],b[N],c[N],ans[N],fac[N],a0[N]; 54 55 void mulpoly(int P){ 56 m=2*n; 57 int L=0,n; 58 for(n=1;n<=m;n<<=1) L++; 59 for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); 60 fnt(a,n,1,P); fnt(b,n,1,P); 61 for(int i=0;i<n;i++) c[i]=mul(a[i],b[i],P); 62 fnt(c,n,-1,P); 63 for(int i=0;i<=n;i++) a[i]=b[i]=0; 64 } 65 66 bool cmp(int a,int b){ 67 return a>b; 68 } 69 70 int inv(int x,int P){ 71 return qpow(x,P-2,P); 72 } 73 74 int main(){ 75 int T; 76 scanf("%d",&T); 77 while(T--){ 78 scanf("%d",&n); 79 for(int i=1;i<=n;i++) scanf("%d",&a0[i]); 80 sort(a0+1,a0+n+1,cmp); 81 fac[0]=1; 82 for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i,mod0); 83 for(int i=1;i<=n;i++){ 84 a0[i]=mul(a0[i]%mod0,qpow(2,n-i,mod0),mod0); 85 a0[i]=mul(a0[i],fac[i-1],mod0); 86 } 87 for(int i=0;i<=n;i++){ 88 a[i]=a0[n-i]; 89 b[i]=inv(fac[i],mod0); 90 } 91 mulpoly(mod0); 92 for(int i=1;i<=n;i++) ans[i]=mul(c[n-i], inv(fac[i-1],mod0),mod0); 93 for(int i=1;i<=n;i++) ans[i] = add(ans[i],ans[i-1],mod0); 94 for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?' ':' '); 95 } 96 return 0; 97 }