BOJ 26399

 

https://www.acmicpc.net/problem/26399

 

코드

http://boj.kr/6e9dc3dd260c444491dc44c13cdde2ef

 

COCI 2022/2023 Contest #2 3

 

난이도 : P1

 

Elapse Time : 실패

 

문제를 보고 30분 동안은 어떤 것도 떠오르지 않아 생각만 했다. 30분간 고민한 뒤 생각한 것은 길이 200000짜리 bitset을 만들어서 $k$번째 색깔의 램프는 bitset의 $k$번째 원소에 표시를 해놓고 2차원 누적합을 만들어 놓는 것이다. 직사각형 영역 내 모든 bitset을 xor 했을 때 bitset의 모든 원소가 0이 되면 그 직사각형에는 모든 램프가 쌍을 이루는 것이 보장된다. 하지만 $O(nmk)$의 공간복잡도를 감당할 수 없었고 풀지 못했다.

 

해싱이라는 태그를 보고 $k$번째 색깔의 램프 2개를 각각 $41^k(\mathrm{mod}\;998244353)$, $-41^k(\mathrm{mod}\;998244353)$에 대응시키고,  $59^k(\mathrm{mod}\;1000000007)$, $-59^k(\mathrm{mod}\;1000000007)$에 대응시켜 2개의 누적합을 만들어놓고 두 누적합 모두에서 합이 각각의 소수에 나누어 떨어지는 직사각형 영역의 개수를 구하는 것으로 풀었다. 직사각형 영역의 개수를 구하는 것은 $0\leq i<j\leq n$인 모든 $(i,j)$에 대해 $sm[z]$에 $i\leq x\leq j$, $0\leq x\leq z$를 만족하는 직사각형 영역의 합을 앞서 구해놓은 두 가지의 누적합으로 계산하여 저장해 놓는다. 그러면 $sm$안에서 두 종류의 누적합이 모두 같은 쌍의 개수를 $O(mlogm)$에 구할 수 있으므로 답을 $O(n^2mlogm)$의 시간에 구할 수 있다.

 

COCI 에디토리얼을 보고 훨씬 더 편한 해싱 방법이 있다는 것을 배웠다. 그냥 $i$번째 색깔에 $2^{60}$미만의 랜덤한 수를 배정해 놓고 직사각형 영역 안에 있는 수들을 bitwise xor 했을 때 0이 되는지 보는 것이다. 특정 직사각형 영역에서 쌍이 맞지 않음에도 0이 될 확률은 $2^{-60}$이고 직사각형 영역이 최대 $5\times10^9$개 정도 있으므로 충돌이 일어날 가능성이 매우 낮다. 직사각형 영역의 개수를 구하는 것은 누적 bitwise xor을 구해놓고 내가 구한 방법과 동일하게 구해주면 된다.