SWERC 2019 H번 문제이다. BOJ 18300번이기도 하다.
Solution
문제에 주어진 점화식이 수학적 의미가 거의 없다는 데 주목하자. $S_{i}$로부터 $S_{i-1}$을 알아내기도 쉽지 않고, 기우성을 분석하기도 쉽지 않다. 따라서 $S_{i}$를 “전부 미리 돌아보지” 않는 이상 접근이 어려울 것이라는 생각을 하게 된다.
실제로 $\set{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$으로부터 사이클의 크기를 추론하면 된다.