레이팅 미적용농부 존은 길이 \(N\)(\(1 \leq N \leq 10^9\))의 이진 문자열을 가지고 있으며, 처음에는 모두 0이다.
그는 먼저 문자열에 \(M\)개(\(1 \leq M \leq 2 \cdot 10^5\))의 갱신을 순서대로 수행한다. 각 갱신은 \(l\)부터 \(r\)까지의 모든 문자를 뒤집는다. 구체적으로, 문자를 뒤집으면 \(0\)은 \(1\)로, \(1\)은 \(0\)으로 바뀐다.
그다음 그는 \(Q\)개(\(1 \leq Q \leq 2 \cdot 10^5\))의 쿼리를 묻는다. 각 쿼리에서 그는 \(l\)부터 \(r\)까지의 부분 문자열의 문자들로 이루어진 길이 \(k\)의 사전순으로 가장 큰 부분 수열을 출력하도록 요청한다. 답이 이진 문자열 \(s_1s_2 \dots s_k\)라면, \(\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}\)(즉, 이진수로 해석했을 때의 값)를 \(10^9+7\)로 나눈 나머지를 출력한다.
부분 수열은 어떤 문자열에서 일부 문자를 삭제하거나 하나도 삭제하지 않고, 남은 문자들의 순서를 바꾸지 않은 채 얻을 수 있는 문자열이다.
길이가 같은 문자열 \(A\)가 문자열 \(B\)보다 사전순으로 크다는 것은, \(A_i \neq B_i\)인 첫 번째 위치 \(i\)가 존재하고 그 위치에서 \(A_i > B_i\)인 것과 동치임을 상기하라.
Problem credits: Chongtian Ma
배점
- 입력 4: \(N \leq 10, Q \leq 1000\)
- 입력 5: \(M \leq 10\)
- 입력 6-7: \(N, Q \leq 1000\)
- 입력 8-12: \(N \leq 2 \cdot 10^5\)
- 입력 13-20: 추가 제약이 없다.
Problem credits: Chongtian Ma
첫째 줄에 \(N\), \(M\), \(Q\)가 주어진다.
다음 \(M\)개의 줄에 각 갱신의 양 끝점인 두 정수 \(l\)과 \(r\)(\(1 \leq l \leq r \leq N\))이 주어진다.
다음 \(Q\)개의 줄에 각 쿼리의 양 끝점과 부분 수열의 길이인 세 정수 \(l\), \(r\), \(k\)(\(1 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1\))가 주어진다.
\(Q\)개의 줄을 출력한다. \(i\)번째 줄에 \(i\)번째 쿼리의 답을 출력한다.
5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 121
13
7
3
1
5
5
3
1After performing the \(M\) operations, the string is \(10101\).
For the first query, there is only one subsequence of length \(5\), \(10101\), which
is interpreted as
\(1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21\).
For the second query, there are \(5\) unique subsequences of length \(4\): \(0101\),
\(1101\), \(1001\), \(1011\), \(1010\). The lexicographically largest subsequence is
\(1101\), which is interpreted as
\(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13\).
For the third query, the lexicographically largest sequence is \(111\), which is
interpreted as \(7\).
9 1 1
7 9
1 8 8330 1 1
1 30
1 30 3073741816Make sure to output the answer modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Gold