| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 17 | 15 | 13 | 86.667% |
경곽이는 길이 $N$인 이진 수열 $A = \left(A_1, \, A_2, \cdots, \, A_{N}\right)$를 발견하였다! 이진 수열이므로 수열의 각 원소는 $0$ 또는 $1$이다.
경곽이는 이 수열에 적용할 $K$개의 구간 쿼리를 가지고 있다. 각 쿼리는 정수 쌍 $(l_i, \, r_i)$로 주어지며, 이는 수열의 $l_i$번째 수부터 $r_i$번째 수까지인 $A_{l_i}, \, A_{l_i + 1}, \, \cdots, A_{r_i}$ 각각을 전부 반전(Flip)하는 연산을 의미한다. 다시 말해, $0$은 $1$로, $1$은 $0$으로 바뀐다.
경곽이는 각 쿼리를 수행할지 말지를 자유롭게 선택할 수 있다. 단, 쿼리의 순서는 변경할 수 없으며, 쿼리를 하나도 수행하지 않는 경우도 허용된다. 따라서, $K$개의 쿼리에 대해 총 $2^K$가지의 수행 조합이 존재하게 된다.
최종적인 수열 $A^\prime = \left(A^\prime_1, \, A^\prime_2, \cdots, \, A^\prime_{N}\right)$의 점수는 모든 수가 $1$인 연속 부분 수열의 개수이다. 예를 들어, 수열 $\left(1, \, 1, \, 0, \, 1, \, 1, \, 1\right)$은 아래와 같이 총 $9$개의 모두 $1$인 연속 부분 수열이 존재하므로 점수는 $9$이다.
경곽이는 가능한 $2^K$가지의 경우에 대해, 쿼리를 적용한 후 수열의 점수의 총합을 구하고자 한다. 이를 $998 \, 244 \, 353$으로 나눈 나머지를 구해보자. $998 \, 244 \, 353$은 소수다.
첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $K$가 공백으로 구분되어 주어진다. ($1 \leq N, \, K < 64$)
두 번째 줄에 길이 $N$인 이진 수열의 원소 $A_1, \, A_2, \, \cdots, \, A_N$이 공백으로 구분되어 주어진다. ($A_i \in \left\{ 0, \,1 \right\}$)
세 번째 줄부터 $K$개의 줄에 걸쳐 쿼리를 나타내는 두 정수 $l_i$, $r_i$가 공백으로 구분되어 주어진다. ($1 \leq l_i \leq r_i \leq N$)
첫 번째 줄에 점수의 총합을 $998 \, 244 \, 353$으로 나눈 나머지를 출력하라.
5 2 0 1 0 0 0 1 3 3 5
17
가능한 쿼리 수행 조합은 $2^2 = 4$가지이다:
따라서 점수의 총합은 $17$이다.
School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 J번