SWERC 2019 H. "Pseudo Random Number Generator"

algorithm-ps ― [ swerc-2019 , BOJ ]

SWERC 2019 H번 문제이다. BOJ 18300번이기도 하다.

Solution

문제에 주어진 점화식이 수학적 의미가 거의 없다는 데 주목하자. \(S_{i}\)로부터 \(S_{i-1}\)을 알아내기도 쉽지 않고, 기우성을 분석하기도 쉽지 않다. 따라서 \(S_{i}\)를 “전부 미리 돌아보지” 않는 이상 접근이 어려울 것이라는 생각을 하게 된다.

실제로 \(\{S_{n}\}\)에는 어느 순간부터 $3 \times 10^{8}$ 정도 크기의 사이클이 나타난다. 이 값은 $2^{63}$보다 훨씬 작고, 구해야 하는 값인 “\(S_{0},\cdots,S_{n-1}\) 중 짝수의 개수”는 적당히 \(10^{7}\) 개씩 끊어서 DB에 저장해두면 어렵지 않게 구할 수 있다.

사이클이 나타나는 순간을 찾는 게 문제인데, \(3 \times 10^{8}\)이라는 주기도 매우 크기 때문에 값을 모두 저장해가며 구한다면 채점 서버는 물론, 로컬에서도 버티기 어렵다. pollard-rho algorithm에서 했던 것처럼 $S_{n} = S_{2n}$을 만족하는 $n$으로부터 사이클의 크기를 추론하면 된다.

Written on March 4, 2020