Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

A. Array and Peaks

가장 peak가 많은 경우는 floor((n-1)/2) 이므로 m이 더 크면 -1

1~n까지 순서대로 들어있는 배열 a를 만든 뒤, k번째 peak를 만들 때 a[(k+1)*2]와 a[(k+1)*2+1]를 교환 하는 방법으로 peak를 m개만큼 만들면 됨

B. AND Sequences

왼쪽 구간 전체를 &한 값 = 오른쪽 구간 전체를 &한 값 = k라고 하면

전체 구간을 &한 값도 k

[1, 1], [2, n] 또는 [1, n-1], [n, n] 구간을 이렇게 나눴을 때도 각 구간 전체를 &하면 k이므로 a[1] = a[n] = k

배열 안에서 k가 되는 수의 개수를 x라고 하면 x가 2미만일 때의 답은 0, 2이상이면 답은 x*(x-1)*(n-2)!

C. Add One

먼저 a[i][j] = 0을 i번 operation했을 때 나오는 숫자의 j의 개수가 되게 전처리를 한다

n을 입력받고, 0~9가 n의 각 자릿수에서 몇번씩 나오는지 센다 (v[i] = n에서 i의 개수)

[0, 9]에 속하는 모든 i, j에 대해 v[i] * a[m+i][j]의 총 합을 구하면 된다(x를 m번 operation하는 것은 0을 x + m번 operation하는 것과 같기 때문)