2016-08-24

HDU 5829 Rikka with Subset【NTT】

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5829

题意：

给定数组$a$，对于$[1,n]$中的每一个$k$，求出数组的所有子集中前$k$大的元素之和的和。

分析：

首先看模数$998244353$，费马素数，原根为$3$，猜想会有$fft$优化一下。
考虑每个元素对于每个$k$的贡献，设$f[k]:=每个元素作为第k大元素，对总和的贡献$
对数组从大到小排个序，设数组下标从$1$开始，则有$f_k= \sum_{i=k}^n\binom{i-1}{k-1} 2^{n-i} a_i$
化简之后得，$f_k =\frac{1}{2^k(k-1)!}\sum_{i=0}^{n-k}\frac{(i+k-1)!}{i!}2^{n-i}a_{i+k}$
设$A_i = \frac{2^{n-i}}{i!}，B_i = (i-1)!a_i$，
则$f_k = \frac{1}{2^k(k-1)!}\sum_{i=0}^{n-k}A_i \times B_{i+k}$
试着将其转化为卷积的形式，将数组$B$倒序，即令$B_{i+k} = B’_{n-k-i}$
$f_k=\frac{1}{2^k(k-1)!}\sum_{i=0}^{n-k}A_i \times B’_{n-k-i} $，至此就转化为卷积的形式了，直接$NTT$即可。
注意最后$f_k$是和$A_{n-k}$对应。

代码：

/*************************************************************************
    > File Name: 5829.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/24 8:43:01
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, mod = 998244353, g = 3;
int n; 
typedef long long ll;
ll A[maxn << 2], B[maxn << 2];
ll a[maxn];
ll Pow(ll a, ll n) 
{
    ll ret = 1;
	for(; n; n >>= 1, a = a * a % mod){
		if(n & 1) ret = ret * a % mod;
	}
    return ret;
}
void NTT(ll y[], int len, int op) 
{
    for(int i = 1, j = len / 2; i < len - 1; i++) {
        if(i < j) swap(y[i], y[j]);
        int k = len / 2;
        while(j >= k) {
            j -= k;
            k /= 2;
        }
        if(j < k) j += k;
    }
    for(int h = 2; h <= len; h <<= 1) {
        ll wn = Pow(g, (mod - 1) / h);
        if(op == -1) wn = Pow(wn, mod - 2);
        for(int j = 0; j < len; j += h) {
            ll w = 1;
            for(int k = j; k < j + h / 2; k++) {
                ll u = y[k];
                ll t = w * y[k + h / 2] % mod;
                y[k] = (u + t) % mod;
                y[k+h/2] = (u - t + mod) % mod;
                w = w * wn % mod;
            }
        }
    }
    if(op == -1) {
        ll t = Pow(len, mod - 2);
        for(int i = 0; i < len; i++)
            y[i] = y[i] * t % mod;
    }
}
ll inv[maxn], two[maxn], fact[maxn];
void init()
{
	two[0] = 1;inv[0] = 1;fact[0] = 1;
	for(int i = 1; i < maxn; i++){
		inv[i] = inv[i - 1] * Pow(i, mod - 2) % mod;
		fact[i] = fact[i - 1] * i % mod;
		two[i] = two[i - 1] * 2 % mod;
	}
}
int main()
{
	init();
	int T;scanf("%d", &T);
	while(T--){
		memset(A, 0, sizeof(A));
		memset(B, 0, sizeof(B));
		int n;scanf("%d", &n);
		int x;
		for(int i = 0; i < n; i++){
			scanf("%I64d", &a[i]);
		}
		sort(a, a + n, greater<int>());
		for(int i = 0; i < n; i++)cout<<a[i]<<' ';
		cout<<endl;
		for(int i = 0; i < n; i++){
			A[i] = two[n - i] * inv[i] % mod;
			B[n - 1 - i] = fact[i] * a[i] % mod;
		}
		int k;
		int l = 2 * n;
		for(k = 1; k < l; k <<= 1);
		l = k;
	    NTT(A, l, 1), NTT(B, l, 1);
    	for(int i = 0; i < l; i ++){
			A[i] = A[i] * B[i] % mod;
		}
		NTT(A, l, -1);
		ll ans = 0;
		ll invtot = 1;
		ll invtwo = Pow(2, mod - 2);
		for(int i = 1; i <= n; i++){
			invtot = invtot * invtwo % mod;
			(ans += inv[i - 1] * A[n - i] % mod * invtot % mod) %= mod;
			printf("%I64d ", ans);
		}
		puts("");
	}
    return 0;
}