题目大意：给你一个长度为$n$的自然数序列$a$，定义一段区间的权值为这一段区间里所有数的和，分别输出权值为$[0,\sum a_{i}]$的区间的长度之和

想到了生成函数的话，这道题并不难做。但很多细节真是不太好搞

我们首先预处理出前缀和s，那么一段区间$[l,r]$的权值就是$s_{r}-s_{l-1}$

容易联想到卷积

第一个多项式是 区间右端点的前缀和 作为指数的生成函数，每一项的系数是 右端点的编号之和

第二个多项式是 区间左端点的前缀和 作为指数的生成函数，每一项的系数是 左端点的编号之和

然而区间长度是相减而不是相乘

我们可以把问题转化成 右端点编号$*1$-左端点编号$*1$，求两次卷积再相减即可

然而左端点的前缀和是负数，我们把生成函数整体右移

然而序列里还有$0$的情况

如果序列里出现了连续的$0$，我们发现这部分答案我们无法通过卷积统计

因为按照我们的方法，在多项式对应的相同的位置卷积的话，两次统计的答案就被减掉了

所以连续的$0$对答案的影响通过$O(n)$扫一遍统计

每新加入一个新的$0$，就会多产生一个等差数列的贡献

另外答案比较大，$FFT$需要开$long\;double$

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #define N1 (1<<18)  6 #define M1 (N1<<1)  7 #define il inline  8 #define dd double  9 #define ld long double 10 #define ll long long 11 using namespace std; 12  13 int T,n; 14  15 int gint() 16 { 17     int ret=0,fh=1;char c=getchar(); 18     while(c<'0'||c>'9'){
   if(c=='-')fh=-1;c=getchar();} 19     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 20     return ret*fh; 21 } 22  23 const ld pi=acos(-1); 24 struct cp{ 25 ld x,y; 26 friend cp operator + (const cp &s1,const cp &s2){ return (cp){s1.x+s2.x,s1.y+s2.y}; } 27 friend cp operator - (const cp &s1,const cp &s2){ return (cp){s1.x-s2.x,s1.y-s2.y}; } 28 friend cp operator * (const cp &s1,const cp &s2){ return (cp){s1.x*s2.x-s1.y*s2.y,s1.y*s2.x+s1.x*s2.y}; } 29 }a[N1],b[N1],c[N1]; 30 int r[N1]; 31 void FFT(cp *s,int len,int type) 32 { 33     int i,j,k; cp wn,w,t; 34     for(i=0;i
         
          >1);j++,w=w*wn) 42             { 43                 t=w*s[i+j+(k>>1)]; 44                 s[i+j+(k>>1)]=s[i+j]-t; 45                 s[i+j]=s[i+j]+t; 46             } 47         } 48     } 49 } 50 void FFT_Main(int len) 51 { 52     FFT(a,len,1); FFT(b,len,1); 53     for(int i=0;i
          
           >1]>>1)|((i&1)<<(L-1)); 80 81 memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); 82 for(i=0;i<=n;i++) a[s[i]].x+=i; 83 for(i=0;i<=n;i++) b[-s[i]+maxn].x++; 84 FFT_Main(len); 85 for(i=maxn;i<=(maxn<<1);i++) ans[i-maxn]=(ll)(c[i].x+0.5); 86 87 memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); 88 for(i=0;i<=n;i++) a[s[i]].x++; 89 for(i=0;i<=n;i++) b[-s[i]+maxn].x+=i; 90 FFT_Main(len); 91 for(i=maxn;i<=(maxn<<1);i++) ans[i-maxn]-=(ll)(c[i].x+0.5); 92 93 for(i=1,num=0;i<=n;i++) 94 if(!v[i]){ num++; ans[0]+=1ll*(num+1)*(num)/2ll; } 95 else{ num=0; } 96 for(i=0;i<=maxn;i++) printf("%lld\n",ans[i]); 97 //puts(""); 98 } 99 return 0;100 101 }