题意

给出一个长度为n的非负整数序列a，设s表示a的前缀和，对于所有的0≤i≤sn" role="presentation">0≤i≤sn$0\le i\le s_n$，求所有和为i的子区间的长度和。
n≤105,sn≤5∗104" role="presentation">n≤105,sn≤5?104$n\le {10}^5,s_n\le 5?{10}^4$

分析

看到这种不管怎么暴力搞都要O(n2)" role="presentation">O(n2)$O(n^2)$的题目就应该想到FFT了。
这个构造还是比较巧妙的，不难发现答案就是(∑ixsi)(∑x−si−1)−(∑xsi)((i−1)x−si−1)" role="presentation">(∑ixsi)(∑x?si?1)?(∑xsi)((i?1)x?si?1)$$(\sum i{x}^{s_i})(\sum x^{?s_{i?1}})?(\sum x^{s_i})((i?1)x^{?s_{i?1}})$$
直接大力FFT就好了。
其中i=0" role="presentation">i=0$i=0$的答案要特殊算。

代码

#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
typedef long double ldb;

const int N=100005;
const ldb pi=acos(-1.0);

int n,s[N],L,rev[N*2];
LL ans[N],sum[N];
struct com
{
    ldb x,y;
    com operator + (const com &d) const {return (com){x+d.x,y+d.y};}
    com operator - (const com &d) const {return (com){x-d.x,y-d.y};}
    com operator * (const com &d) const {return (com){x*d.x-y*d.y,x*d.y+y*d.x};}
    com operator / (const ldb &d) const {return (com){x/d,y/d};}
}a[N*2],b[N*2];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void FFT(com *a,int f)
{
    for (int i=0;i>1]>>1)|((i&1)<<(lg-1));
        for (int i=s[n]+1;i