題意通り f(x)f(x)f(x) を計算すると、 O(NX)O(NX)O(NX) の計算量が必要となり、間に合いません。 そこで、F(x)=f(0)+f(1)+⋯+f(x) (F(x) = f(0) + f(1) + \cdots + f(x) \ (F(x)=f(0)+f(1)+⋯+f(x) ( 便宜上 f(0)=0f(0) = 0f(0)=0 とする ))) の 累積和 を用いて、 f(x)=F(x)−F(x−N−1)f(x) = F(x) - F(x-N-1)f(x)=F(x)−F(x−N−1) と計算し高速化することで、 O(N+X)O(N+X)O(N+X) で解くことができます。
