InputThe first line of the input is a single integer T (T=5)T (T=5), indicating the number of testcases.
For each testcase, the first line contains one integer nn. The second line contains nnnon-negative integers, which mean the length of every section. If we denote the total length of all the sections as ss, we can guarantee that 0≤s≤500000≤s≤50000 and 1≤n≤1000001≤n≤100000.
OutputFor each testcase, print s+1s+1 lines. The single number in the ii-th line indicates the total pleasure JRY can get if he races all the ways of length i−1i−1.
Sample Input
2
3
1 2 3
4
0 1 2 3
Sample Output
0
1
1
3
0
2
3
1
3
1
6
0
2
7
题意：总区间中有n个数(n<=100000)，求每种区间和，累加出所对应的区间长度(j-i+1)和；
思路：可以通过母函数得到方程，然后FFT求。 也有一种暴力一点的方式，分治+FFT：即求跨过每个点的区间的贡献。 然后两次FFT分别算出左边和右边的贡献。
（4900ms卡过去了。要用long double。
母函数的方法可以看：https://blog.csdn.net/kyleyoung_ymj/article/details/51712329
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rep2(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int maxn=;
const double pi=acos(-1.0);
struct cp
{
double r,i;
cp(){}
cp(double rr,double ii):r(rr),i(ii){}
cp operator +(const cp&x)const{return cp(r+x.r,i+x.i);}
cp operator -(const cp&x)const{return cp(r-x.r,i-x.i);}
cp operator *(const cp&x)const{return cp(r*x.r-i*x.i,i*x.r+r*x.i);}
};
ll ans[maxn];int s[maxn],sum[maxn],R[maxn],n;
cp a[maxn],b[maxn],W,w,p;
void read(int &x){
x=; char c=getchar();
while(c>''||c<'') c=getchar();
while(c>=''&&c<='') x=x*+c-'',c=getchar();
}
inline void fft(cp*c,int t)
{
int i,j,k;
for(i=;i<n;i++) R[i]<i?swap(c[R[i]],c[i]),:;
for(i=;i<n;i<<=)
for(j=,W={cos(pi/i),sin(pi/i)*t};j<n;j+=i<<)
for(k=,w={,};k<i;k++,w=w*W)
p=c[j+k+i]*w,c[j+k+i]=c[j+k]-p,c[j+k]=c[j+k]+p;
}
void solve(int l,int r)
{
if(l==r){ ans[s[l]]++; return ;}
int mid=(l+r)>> ,delta=sum[r]-sum[l-];
solve(l,mid); solve(mid+,r);
for(n=;(n-)<=delta;n<<=);
rep(i,,n-) R[i]=R[i>>]>>|(i&?n>>:); rep2(i,mid,l) a[sum[mid]-sum[i-]].r+=mid-i+;
rep(i,mid+,r) ++b[sum[i]-sum[mid]].r;
fft(a,); fft(b,);
rep(i,,n-) a[i]=a[i]*b[i];
fft(a,-);
rep(i,,delta) ans[i]+=(ll)((a[i].r)/n+0.5);
rep(i,,n) a[i]=b[i]=cp(.,.); rep2(i,mid,l) ++a[sum[mid]-sum[i-]].r;
rep(i,mid+,r) b[sum[i]-sum[mid]].r+=i-mid;
fft(a,); fft(b,);
rep(i,,n-) a[i]=a[i]*b[i];
fft(a,-);
rep(i,,delta) ans[i]+=(ll)((a[i].r)/n+0.5);
rep(i,,n) a[i]=b[i]=cp(.,.);
}
int main()
{
int N,T;
scanf("%d",&T);
while(T--){
read(N);
rep(i,,N) read(s[i]),sum[i]=sum[i-]+s[i];
rep(i,,sum[N]) ans[i]=;
solve(,N);
rep(i,,sum[N]) printf("%lld\n",ans[i]);
}
return ;
}