作者：永无止境 | 来源：互联网 | 2023-09-13 20:35
Asweknow,Rikkaispooratmath.Yutaisworryingaboutthissituation,sohegivesRikkasomem
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?
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
#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=3;
const int maxn=268576;
const int Mod=998244353;
int qpow(int v,int p)
{
int ans=1;
for(;p;p>>=1,v=1ll*v*v%Mod)
if(p&1)ans=1ll*ans*v%Mod;
return ans;
}
void rader(int y[], int len) {
for(int i=1,j=len/2;i1;i++) {
if(i<j) swap(y[i],y[j]);
int k=len/2;
while(j>=k) j-=k,k/=2;
if(jk;
}
}
void NTT(int y[],int len,int opt) {
rader(y,len);
for(int h=2;h<=len;h<<=1) {
int wn=qpow(G,(MOD-1)/h);
if(opt==-1) wn=qpow(wn,Mod-2);
for(int j=0;jh) {
int w=1;
for(int k=j;k2;k++) {
int u=y[k];
int t=(ll)w*y[k+h/2]%MOD;
y[k]=(u+t)%MOD;
y[k+h/2]=(u-t+MOD)%MOD;
w=(ll)w*wn%MOD;
}
}
}
if(opt==-1) {
int t=qpow(len,MOD-2);
for(int i=0;iMOD;
}
}
int inv[maxn],A[maxn],B[maxn],a[maxn],f[maxn],p2[maxn];
int main() {
int T,N;
f[0]=inv[0]=p2[0]=1;
rep(i,1,100000) p2[i]=(ll)p2[i-1]*2%Mod;
rep(i,1,100000) f[i]=(ll)f[i-1]*i%Mod;
inv[100000]=qpow(f[100000],Mod-2);
for(int i=100000-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%Mod;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
int len=1; while(len<=N*2) len<<=1;
rep(i,0,len) A[i]=B[i]=0;
rep(i,1,N) scanf("%d",&a[i]);
sort(a+1,a+N+1); reverse(a+1,a+N+1);
rep(i,0,N-1){
A[i]=inv[i];
B[i]=(ll)f[N-i-1]*p2[i]%Mod*a[N-i]%Mod;
}
NTT(A,len,1); NTT(B,len,1);
rep(i,0,len-1) A[i]=(ll)A[i]*B[i]%Mod; //乘完，不能只乘到N
NTT(A,len,-1); int ans=0;
rep(i,1,N){
(ans+=(ll)inv[i-1]*A[N-i]%Mod)%=Mod;
printf("%d ",ans);
}
puts("");
}
return 0;
}
京公网安备 11010802041100号