hdu_5829 Rikka with Subset

题目:

  As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
  Yuta has n numbers A[1]~A[n] and a number K. For any none empty subset S of the numbers, the value of S is equal to the sum of the largest min(|S|,k) numbers in S. The value of the array A is equal to the sum of the value of all none empty subset of the numbers.
  Now Yuta shows the n numbers, And he wants to know the value of the array for each K in [1,n].
  It is too difficult for Rikka. Can you help her?

思路:

  为了每次单独考虑一个元素,所以改成求每个元素作为第 大的元素出现在子序列中的方案数。那么如果先对整个序列排序,如果第 个元素要作为 大出现在序列中,那么 中一定要选中 个, 就任意了。
  所以第 大的元素对答案的贡献就是 。把组合数展开,拆出一个次数为 ,一个次数为 ,用NTT乘一下就行了。
  最后的答案就是 ,复杂度

代码:

#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int MOD=998244353,N=(1<<18)+5;

int qkpow(int x,int k){
    int ans=1;
    for(;k;k>>=1,x=(ll)x*x%MOD)
        if(k&1)ans=(ll)ans*x%MOD;
    return ans;
}
int inv(int x){
    return qkpow(x,MOD-2);
}

int rev[N];
void ntt(int a[],int n,bool inv_f){
    rep(i,0,n-1)
        if(rev[i]<i)
            std::swap(a[i],a[rev[i]]);
    for(int l=2,m=1;l<=n;l<<=1,m<<=1){
        int base=qkpow(3,(MOD-1)/l);
        if(inv_f)base=inv(base);
        for(int *p=a;p!=a+n;p+=l){
            int w=1;
            rep(i,0,m-1){
                int t=(ll)w*p[i+m]%MOD;
                p[i+m]=(p[i]-t+MOD)%MOD;
                p[i]=(p[i]+t)%MOD;
                w=(ll)w*base%MOD;
            }
        }
    }
    int invn=inv(n);
    if(inv_f)
        rep(i,0,n-1)
            a[i]=(ll)a[i]*invn%MOD;
}

int log2(int x){
    int res=0;
    while((1<<res)<x)res++;
    return res;
}

int fac[N],pw2[N];//fac[i]=i!,pw2[i]=2^i
int ifac[N],ipw2[N];
void init(){
    int n=N-5;
    fac[0]=pw2[0]=1;
    ipw2[0]=inv(pw2[0]);
    ifac[0]=inv(fac[0]);
    rep(i,1,n){
        fac[i]=(ll)fac[i-1]*i%MOD;
        pw2[i]=(pw2[i-1]<<1)%MOD;
        ifac[i]=inv(fac[i]);
        ipw2[i]=inv(pw2[i]);
    }
}

int a[N],b[N],c[N],res[N];
int main(){
    // freopen("data.in","r",stdin);
    init();
    int cas,n;
    scanf("%d",&cas);
    while(cas--){
        mset(b,0);mset(c,0);
        scanf("%d",&n);
        rep(i,1,n)
            scanf("%d",a+i);
        std::sort(a+1,a+1+n,std::greater<int>());
        rep(i,1,n)
            b[i]=(ll)a[i]*ipw2[i]%MOD*fac[i-1]%MOD;
        rep(i,0,n)
            c[n-i]=ifac[i];

        int lim=log2((n+1)*2),d=(1<<lim);
        rep(i,0,d-1)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));
        ntt(b,d,false);ntt(c,d,false);
        rep(i,0,d-1)
            b[i]=(ll)b[i]*c[i]%MOD;
        ntt(b,d,true);

        rep(i,1,n){
            res[i]=(ll)b[i+n]*ifac[i-1]%MOD*pw2[n]%MOD;
            (res[i]+=res[i-1])%=MOD;
        }
        rep(i,1,n)
            printf("%d ",res[i]);
        puts("");
    }
    return 0;
}