길이가 동일한 수열 X = (x0, x1, …, xn-1)와 Y = (y0, y1, …, yn-1)가 있다.

이 두 수열의 각 원소는 음이 아닌 정수이다.

다음은 n=5인 경우의 한 예이다.

X = (1, 0, 0, 0, 1)

Y = (0, 5, 2, 0, 1)

임의의 정수 t가 주어졌을 때 XCorr(t)는 다음과 같이 정의된다.

XCorr(t)=\displaystyle\sum_{i=0}^{n-1}{x_iy_{i+t}}

(i < 0 이거나 i ≥ n 이면 x_i = y_i = 0으로 간주한다.)

예를 들어 t가 0, 1, -1일 때, XCorr(t)값은 다음과 같이 계산된다.

XCorr(0) = x_0y_0 + x_1y_1 + \dots + x_{n-1}y_{n-1}

XCorr(1) = x_0y_1 + x_1y_2 + \dots + x_{n-1}y_n

회색 칸에 들어있는 부분은 계산결과에 영향을 주지 않음에 유의하라. y_0는 계산식에 포함되지 않고 x_n-1은 곱해지는 y_n = 0이므로 계산 결과에 영향을 주지 않는다. 따라서 예시 수열 X와 Y에서 XCorr(1)은 다음과 같이 계산할 수 있다.

1\times5+0\times2+0\times0+0\times1=5

XCorr(-1) = x_0y_{-1} + x_1y_0 + \dots + x_{n-1}y_{n-2}

임의의 t값의 범위 ( a ≤ t ≤ b)에 대해 XCorr(t)를 모두 구해서 더한 값 S(a, b)는 다음과 같이 정의된다.

S(a,b)=\displaystyle\sum_{a \le t \le b}{XCorr(t)}

수열 X, Y와 t의 범위 a, b가 주어졌을 때 S(a, b)를 구하는 프로그램을 작성하시오.

XCorr timer 1초 memory 128MB

XCorr 1초 128MB