HDU - 5829:Rikka with Subset (NTT)
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?
InputThe 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).OutputFor 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
题意:给定一个数组,F(k)表示所有集合s的前min(K,s)大之和。求所有F(k)。
思路:先得到方程f(x),然后一般来说一个组合数*一个指数,可以直接转化一下用NTT加速;或者用第二类斯特林转化,再套NTT或FFT卷积。
关键在于找到某两个系数之和为定值,然后分别以其为“基”构造函数,然后取卷积这两个函数。
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define ll long long
#define MOD Mod
const int G=;
const int maxn=;
const int Mod=;
int qpow(int v,int p)
{
int ans=;
for(;p;p>>=,v=1ll*v*v%Mod)
if(p&)ans=1ll*ans*v%Mod;
return ans;
}
void rader(int y[], int len) {
for(int i=,j=len/;i<len-;i++) {
if(i<j) swap(y[i],y[j]);
int k=len/;
while(j>=k) j-=k,k/=;
if(j<k) j+=k;
}
}
void NTT(int y[],int len,int opt) {
rader(y,len);
for(int h=;h<=len;h<<=) {
int wn=qpow(G,(MOD-)/h);
if(opt==-) wn=qpow(wn,Mod-);
for(int j=;j<len;j+=h) {
int w=;
for(int k=j;k<j+h/;k++) {
int u=y[k];
int t=(ll)w*y[k+h/]%MOD;
y[k]=(u+t)%MOD;
y[k+h/]=(u-t+MOD)%MOD;
w=(ll)w*wn%MOD;
}
}
}
if(opt==-) {
int t=qpow(len,MOD-);
for(int i=;i<len;i++) y[i]=(ll)y[i]*t%MOD;
}
}
int inv[maxn],A[maxn],B[maxn],a[maxn],f[maxn],p2[maxn];
int main() {
int T,N;
f[]=inv[]=p2[]=;
rep(i,,) p2[i]=(ll)p2[i-]*%Mod;
rep(i,,) f[i]=(ll)f[i-]*i%Mod;
inv[]=qpow(f[],Mod-);
for(int i=-;i>=;i--) inv[i]=(ll)inv[i+]*(i+)%Mod;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
int len=; while(len<=N*) len<<=;
rep(i,,len) A[i]=B[i]=;
rep(i,,N) scanf("%d",&a[i]);
sort(a+,a+N+); reverse(a+,a+N+);
rep(i,,N-){
A[i]=inv[i];
B[i]=(ll)f[N-i-]*p2[i]%Mod*a[N-i]%Mod;
} NTT(A,len,); NTT(B,len,);
rep(i,,len-) A[i]=(ll)A[i]*B[i]%Mod; //乘完,不能只乘到N
NTT(A,len,-); int ans=;
rep(i,,N){
(ans+=(ll)inv[i-]*A[N-i]%Mod)%=Mod;
printf("%d ",ans);
}
puts("");
}
return ;
}
最新文章
- 故障恢复和恢复模式(Crash Recovery &; Recovery Models)
- 【HTML5】浅析HTML5应用程序缓存(ApplicationCache)
- BZOJ 2448: 挖油
- Moses与IRSTLM共同编译失败的解决方案:fatal error: dictionary.h no such file or 目录
- [转]webrtc学习: 部署stun和turn服务器
- Actioncontext跟ServletActionContext的区别---未完待续
- COJ 0332 The Flash
- Attrib命令,可以让文件夹彻底的隐藏起来
- JavaScript OOP(一)之构造函数与new命令
- fiddler抓手机报文的配置指南
- DataCleaner第一章
- vue项目结构搭建
- [每天解决一问题系列 - 0007] 如何创建Catalog并用其签名
- 【CSS】定义元素的对齐方式
- node 图片验证码生成
- TensorFlow函数:tf.ones
- gateway-workman
- Cmake编译SDL2
- Linux下的CPU性能瓶颈分析案例
- qi zi
热门文章
- NIO复习02
- Spring 之定义切面尝试(基于 XML)
- Please make sure the TESSDATA_PREFIX environment variable is set to your ";tessdata"; directory.
- JVM调优总结(二)
- SpringBoot ControllerAdvice
- [CF489D]Unbearable Controversy of Being
- HDU 1241 油田
- orecle常用函数
- idea调节字体大小
- scala学习手记14 - 单例对象