HDU5829 ntt

题意：给你一个 A 数组。你要输出所有的T[k]。 T[k] 是指 A 数组的所有子集中前k大的数的和的和。首先破此题需要以下一些知识。

FFT 的原理， NTT 的板子(P需要是费马素数）

假设一个数 g 对于P来说是原根，那么 gi mod P 的结果两两不同,且有 1<g<P,0<i<P ,那么 g 可以称为是P的一个原根,归根到底就是 gP−1≡1(mod P) 当且仅当指数为P-1的时候成立.(这里P是素数).

知道了以上的东西，就能把此问题转化成卷积来做了。

先想想，肯定要排序，倒着或者顺着都行，排序之后发现，第 i 个数对于k的贡献只当它作为集合中最大，第二大…第 k 大的时候才有。那么我们可以想一个比较暴力的方法，枚举每个i作为集合第 k 大的贡献，在求个前缀和，就是答案。

设f[k]为所有数作为第 k 大的时候的和，那么有f[k]=∑ni=kCk−1i−1∗2n−i∗A[i]

f[k]=1(k−1)!∑ni=k(i−1)!(i−k)!∗2n−i∗A[i]

f[k]=12k∗(k−1)!∑n−ki=02n−ii!∗(i+k−1)!∗A[i+k]

以上很像卷积形式了。设 a[i]=2n−ii! b[i]=A[i]∗(i−1)! 把 b 数组reverse一下 b[i+k]=b[n+1−i−k] 再整体左移一位就 b[i+k]=b[n−i−k] 此时已经是卷积形式了。注意最后 f[k]=a[n−k]

// // Created by Running Photon // Copyright (c) 2015 Running Photon. All rights reserved. // #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <string> #include <sstream> #include <set> #include <vector> #include <stack> #define ALL(x) x.begin(), x.end() #define INS(x) inserter(x, x,begin()) #define ll long long #define CLR(x) memset(x, 0, sizeof x) using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 4e5 + 10; const int maxv = 1e3 + 10; const double eps = 1e-9; const ll MOD = 998244353; const ll g = 3; // MOD的原根,当且仅当 g^(MOD-1) = 1 % MOD ll Pow(ll a, ll n) { ll ret = 1; while(n) { if(n & 1) ret = ret * a % MOD; n >>= 1; a = a * a % MOD; } return ret; } void rader(ll y[], int len) { 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; } } void ntt(ll y[], int len, int on) { rader(y, len); for(int h = 2; h <= len; h <<= 1) { ll wn = Pow(g, (MOD-1)/h); if(on == -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(on == -1) { ll t = Pow(len, MOD - 2); for(int i = 0; i < len; i++) y[i] = y[i] * t % MOD; } } ll inv[maxn]; ll fac[maxn]; ll f[maxn]; ll inv2; void init() { inv2 = Pow(2, MOD - 2); inv[1] = inv[0] = 1; fac[0] = fac[1] = 1; for(ll i = 2; i <= 1e5; i++) { inv[i] = inv[i-1] * Pow(i, MOD - 2) % MOD; fac[i] = fac[i-1] * i % MOD; } } ll a[maxn], b[maxn]; ll A[maxn]; int main() { #ifdef LOCAL freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin); freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout); #endif // ios_base::sync_with_stdio(0); int T; scanf("%d", &T); init(); while(T--) { int n; scanf("%d", &n); CLR(A); CLR(a); CLR(b); for(int i = 1; i <= n; i++) { scanf("%I64d", A + i); } sort(A+1, A+n+1, greater<ll>()); for(int i = 0; i < n; i++) { a[i] = inv[i] * Pow(2, n-i) % MOD; } for(int i = 1; i <= n; i++) { b[i] = fac[i-1] * A[i] % MOD; } reverse(b+1, b+1+n); for(int i = 0; i < n; i++) { b[i] = b[i+1]; } b[n] = 0; int len = 1; while(len <= n * 2) len <<= 1; ntt(a, len, 1); ntt(b, len, 1); for(int i = 0; i < len; i++) { a[i] = a[i] * b[i] % MOD; } ntt(a, len, -1); ll r = inv2; for(int i = 1; i <= n; i++) { f[i] = r * inv[i-1] % MOD * a[n-i] % MOD; f[i] = (f[i-1] + f[i]) % MOD; printf("%I64d ", f[i]); r = r * inv2 % MOD; } puts(""); } return 0; }