题意:给你一个
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]
#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;
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
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;
}
转载请注明原文地址: https://ju.6miu.com/read-1291044.html