Rikka with Subset
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 871 Accepted Submission(s): 276
Problem Description
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?
Input
The first line contains a number t(1<=t<=10), the number of the testcases.
For each testcase, the first line contains a number n(1<=n<=100000), the number of numbers Yuta has. The second line contains n number A[1]~A[n](0<=A[i]<=10^9).
Output
For each testcase, print a line contains exactly n numbers, the ith number is the value of the array when K=i. The answer may be very large, so you only need to print the answer module 998244353.
Sample Input
2
3
1 1 1
5
1 2 3 4 5 Sample Output
7 11 12
129 201 231 239 240 Author
學軍中學
Source
2016 Multi-University Training Contest 8
Recommend
wange2014 | We have carefully selected several similar problems for you: 5932 5931 5930 5929 5928
題意：給你一個A數組。你要輸出所有的T[k]。T[k]是指A數組的所有子集中前k大的數的和的和。
題解：FFT的原理，NTT的闆子(P需要是費馬素數...有空我再寫一篇NTT(快速數論變換)的文章吧....
假設一個數g對于P來說是原根，那麼
的結果兩兩不同,且有 1<g<P,0<i<P,那麼g可以稱為是P的一個原根,歸根到底就是
當且僅當指數為P-1的時候成立.(這裡P是素數).
是以這時就可以利用卷積來解決了。
先從大到小排序，排序之後發現，第i個數對于k的貢獻隻當它作為集合中最大，第二大…第k大的時候才有。那麼我們可以想一個比較暴力的方法，枚舉每個i作為集合第k大的貢獻，在求個字首和，就是答案。
設f[k]為所有數作為第k大的時候的和，那麼有
，
，
。
以上就是卷積的套路了。設
，
。先把b數組reverse一下，
，再整體左移一位就是
。此時就是卷積形式了。注意最後是
。
AC代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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 ans = 1;
while(n)
{
if(n & 1) ans = ans * a % mod;
n >>= 1;
a = a * a % mod;
}
return ans;
}
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) //NTT
{
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;
ll a[maxn], b[maxn];
ll A[maxn];
int n;
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;
}
}
void solve()
{
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;
}
void Conv()
{
int len = 1;
while(len <= 2*n) 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);
}
void gao()
{
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("%lld ", f[i]);
r = r * inv2 % mod;
}
puts(""); //最後一個數後也有空格.....
}
int main()
{
int t;
scanf("%d", &t);
init();
while(t--)
{
scanf("%d", &n);
memset(A, 0, sizeof(A));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 1; i <= n; i++)
{
scanf("%lld", &A[i]);
}
sort(A+1, A+n+1, greater<ll>());
solve();
Conv();
gao();
}
return 0;
}