| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 118 | 61 | 59 | 56.190% |
$N + M$개의 게이트로 구성된 회로가 있다. 게이트들은 0ドル$부터 $N + M - 1$까지 번호가 붙어 있다. 게이트 0ドル$부터 $N - 1$까지는 임계 게이트들이고, 게이트 $N$부터 $N + M - 1$까지는 소스 게이트들이다.
게이트 0ドル$을 제외한 각 게이트의 출력은 하나이고 정확히 하나의 임계 게이트의 입력으로 연결된다. 좀더 구체적으로, 각 게이트 $i$의 (1ドル \le i \le N + M - 1$) 출력은 게이트 $P[i]$의 입력이다. (0ドル \le P[i] \le N-1$) 중요하게, $P[i] \lt i$가 항상 성립한다. 또, $P[0] = -1$이다. 즉, 게이트 0ドル$의 출력은 다른 어떤 게이트의 입력으로도 연결되지 않는다. 모든 임계 게이트는 하나 이상의 입력을 가진다. 모든 소스 게이트는 입력이 없다.
각 게이트는 0ドル$ 혹은 1ドル$의 값이 될 수 있는 상태를 가진다. 게이트의 출력은 그 게이트의 상태와 같다. 소스 게이트들의 상태는 입력 배열 $A$로 (배열 크기 $M$) 주어진다. 즉, 각 $j$에 대해 (0ドル \le j \le M - 1$), $A[j]$의 값이 게이트 $N + j$의 상태이다.
각 임계 게이트의 상태는 해당 게이트의 입력에 따라 다음과 같이 결정된다. 각 임계 게이트에는 임계치를 결정하는 파라미터가 정해져 있다. $c$개의 입력을 가진 임계 게이트의 파라미터는 1ドル$ 이상 $c$ 이하의 정수이다. 파라미터가 $p$인 임계 게이트의 상태는, 입력 중 $p$개 이상이 1ドル$인 경우 1ドル$이고, 그렇지 않은 경우 0ドル$이다.
예를 들어, 아래 그림처럼 $N = 3$개의 임계 게이트와 $M = 4$개의 소스 게이트가 있는 회로가 있다고 하자. 게이트 0ドル$의 입력은 게이트 1ドル$과 6ドル$(의 출력)이고, 게이트 1ドル$의 입력은 게이트 2ドル,ドル 4ドル,ドル 5ドル$이며, 게이트 2ドル$의 입력은 게이트 3ドル$이다.
이 회로에서 게이트 3ドル$과 5ドル$의 상태는 1ドル$이고 게이트 4ドル$와 6ドル$의 상태는 0ドル$이라고 하자. 게이트 2ドル,ドル 1ドル,ドル 0ドル$의 파라미터는 각각 1ドル,ドル 2ドル,ドル 2ドル$라고 하자. 이 경우, 게이트 2ドル$의 상태는 1ドル,ドル 게이트 1ドル$의 상태는 1ドル,ドル 게이트 0ドル$의 상태는 0ドル$이 된다. 위의 상황은 아래 그림에 표시되어 있다. 게이트의 상태가 1ドル$인 것들이 검은 색으로 표시되어 있다.
소스 게이트들의 상태는 $Q$번 업데이트된다. 각 업데이트는 두 정수 $L,ドル $R$로 ($N \le L \le R \le N + M - 1$) 표현된다. 업데이트의 의미는 번호가 $L$부터 $R$까지인 모든 소스 게이트의 상태를 뒤집는 것이다. 뒤집는다는 것의 의미는 0ドル$을 1ドル$로, 1ドル$을 0ドル$으로 바꾸는 것이다. 업데이트에 의해 변경된 게이트들의 상태는 이후의 업데이트에 영향을 받지 않는 한 유지된다.
초기 상태를 입력 받고, 각 업데이트 이후에 게이트 0ドル$의 상태가 1ドル$이 되도록 만들 수 있는 임계 게이트 파라미터 설정 방법의 경우의 수를 계산하는 프로그램을 작성하라. 두 파라미터 설정 방법이 다르다는 것은, 임계 게이트 중 하나라도 다른 파라미터 값을 가진다는 것으로 정의된다. 경우의 수 값이 매우 클 수 있으므로 그 값을 1ドル,000円,002円,022円$으로 나눈 나머지를 결과로 제시해야 한다.
위의 예에서 게이트 0ドル,ドル 1ドル,ドル 2ドル$는 각각 2ドル,ドル 3ドル,ドル 1ドル$개의 입력이 있으므로, 가능한 파라미터 설정 방법은 6ドル$가지가 있다. 가능한 방법들 중 2ドル$가지에서 게이트 0ドル$의 상태는 1ドル$이 된다.
다음 2개의 함수를 구현해야 한다.
void init(int N, int M, int[] P, int[] A)
count_ways 호출 이전에 정확히 한번 호출된다.
int count_ways(int L, int R)
다음 호출들을 보자:
init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])
이 회로는 본문에서 설명한 것과 같다.
count_ways(3, 4)
게이트 3ドル$과 4ドル$를 뒤집는다. 즉, 게이트 3ドル$의 상태는 0ドル$이 되고 게이트 4ドル$의 상태는 1ドル$이 된다. 게이트 0ドル$의 상태가 1ドル$이 되게 하는 2ドル$가지 파라미터 설정이 아래 그림에 표현되어 있다.
| 설정 1ドル$ | 설정 2ドル$ |
|---|---|
위의 방법 이외의 모든 다른 설정에서 게이트 0ドル$의 상태가 0ドル$이 된다. 따라서, 이 함수 호출은 2ドル$를 리턴해야 한다.
count_ways(4, 5)
게이트 4ドル$와 5ドル$를 뒤집는다. 모든 소스 게이트의 상태가 0ドル$이 되었다. 이 경우 파라미터 설정을 어떻게 해도 게이트 0ドル$의 상태는 0ドル$이다. 따라서, 이 함수 호출은 0ドル$을 리턴해야 한다.
count_ways(3, 6)
모든 소스 게이트의 상태가 1ドル$로 바뀐다. 이 경우 파라미터 설정을 어떻게 해도 게이트 0ドル$의 상태는 1ドル$이다. 따라서, 이 함수 호출은 6ドル$을 리턴해야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | $N = 1,ドル $M \le 1000,ドル $Q \le 5$ |
| 2 | 7 | $N, M \le 1000,ドル $Q \le 5,ドル 각 임계 게이트에는 정확히 2ドル$개의 입력이 있다. |
| 3 | 9 | $N, M \le 1000,ドル $Q \le 5$ |
| 4 | 4 | $M = N + 1,ドル $M = 2^z$ (양의 정수 $z$), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (1ドル \le i \le N + M - 1$), $L = R$ |
| 5 | 12 | $M = N + 1,ドル $M = 2^z$ (양의 정수 $z$), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (1ドル \le i \le N + M - 1$) |
| 6 | 27 | 각 임계 게이트에는 정확히 2ドル$개의 입력이 있다. |
| 7 | 28 | $N, M \le 5000$ |
| 8 | 11 | 추가적인 제한이 없다. |
샘플 그레이더는 다음의 양식으로 입력을 받는다:
샘플 그레이더는 다음의 출력을 생성한다:
count_ways의 리턴 값Olympiad > International Olympiad in Informatics > IOI 2022 > Day 2 4번
C++17, C++20, C++17 (Clang), C++20 (Clang)