[Round#419 Div.2] D. Karen and Test

http://codeforces.com/contest/816/problem/D

a_1부터 a_N까지 N개의 수열이 있을 때, b_1 = a_1 + a_2, b_2 = a_2 - a_3 ... 이런 식으로 그 다음 줄에 b_n을 만든다.

같은 과정을 반복하여 수열의 수가 1개가 될 때 까지 진행했을 때 나오는 수가 뭔지 구하는 문제이다.

(말보다는 그림이 이해하기 편하니 아래그림 참조)

 첫번째 줄 부터 계산하다 보면 4번째 줄에 와서 규칙성을 찾을 수 있는데, 바로 이항계수이다.

구체적으로 말하면, 1번째 수열들을라 하면, 

5번째 줄에 나타나는 수열들은 형태를 띈다.

즉, 첫 번째 줄에 있는 수열을 라 하면,

4줄 아래있는 5번째 줄에 나타나는 수열은 이 되고,

 

다시 4줄 아래에 있는 9번째 줄에 나타나는 수열은 꼴이 된다.

 

따라서 총 N개의 수가 주어지면 계산되어지는 줄 수는 N-1줄이고, 결국 (N-1)%4 를 기준으로 이항계수를 계수로 갖는 수열들의 합을 구해주면 O(N)만에 풀어낼 수 있다.

위의 예제에서도 5번째 줄에 나타나는 수(결국엔 최종 답)는 1×3+2×9+1×15=36으로 O(N)에 구할 수 있다.