HDU 5829 16多校08 Rikka with Subset （NTT）

最新推荐文章于 2018-11-17 23:22:44 发布

LzyRapX

最新推荐文章于 2018-11-17 23:22:44 发布

阅读量1.1k

点赞数 5

分类专栏： ACM_FFT / NTT HDUOJ 文章标签： HDU 5829 Rikka with Subset NTT 16多校08

本文链接：https://blog.csdn.net/liangzhaoyang1/article/details/52793196

版权

HDUOJ 同时被 2 个专栏收录

304 篇文章 2 订阅

订阅专栏

ACM_FFT / NTT

12 篇文章 0 订阅

订阅专栏

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

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来说是原根，那么 $g^i mod \space P$ 的结果两两不同,且有 1<g<P,0<i<P,那么g可以称为是P的一个原根,归根到底就是 $g^{P-1} \equiv 1 (mod \space P)$ 当且仅当指数为P-1的时候成立.(这里P是素数).

所以这时就可以利用卷积来解决了。
先从大到小排序，排序之后发现，第i个数对于k的贡献只当它作为集合中最大，第二大…第k大的时候才有。那么我们可以想一个比较暴力的方法，枚举每个i作为集合第k大的贡献，在求个前缀和，就是答案。
设f[k]为所有数作为第k大的时候的和，那么有 $f[k] = \sum_{i=k}^{n}C_{i-1}^{k-1}*2^{n-i}*A[i]$ ，

$f[k] = \frac{1}{(k-1)!} \sum_{i=k}^{n} \frac{(i-1)!}{(i-k)!}*2^{n-i}*A[i]$ ，

$f[k] = \frac{1}{2^k*(k-1)!} \sum_{i=0}^{n-k} \frac{2^{n-i}}{i!}*(i+k-1)!*A[i+k]$ 。

以上就是卷积的套路了。设 $a[i]=\frac{2^{n-i}}{i!}$ ， $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]$ 。

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;
}

LzyRapX

关注

5
点赞
踩
1

收藏

觉得还不错? 一键收藏
0
评论
HDU 5829 16多校08 Rikka with Subset （NTT）

Rikka with SubsetTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 871 Accepted Submission(s): 276Problem DescriptionAs we know, Rikk
复制链接

扫一扫