레이팅 미적용베시와 엘시는 \(N\)개(\(1\le N\le 10^5\))의 돌 무더기를 가지고 게임을 한다. \(i\)번째 무더기에는 \(a_i\)개의 돌이 있다 (\(1\le i\le N\), \(1\le a_i\le 10^6\)). 두 소는 번갈아 가며 차례를 진행하고, 베시가 먼저 시작한다.
- 먼저 베시가 어떤 양의 정수 \(s_1\)을 골라, 돌이 \(s_1\)개 이상 있는 어떤 무더기에서 돌 \(s_1\)개를 제거한다.
- 그다음 엘시가 \(s_1\)이 \(s_2\)를 나누도록 하는 어떤 양의 정수 \(s_2\)를 골라, 돌이 \(s_2\)개 이상 있는 어떤 무더기에서 돌 \(s_2\)개를 제거한다.
- 그다음 베시가 \(s_2\)가 \(s_3\)을 나누도록 하는 어떤 양의 정수 \(s_3\)을 골라, 돌이 \(s_3\)개 이상 있는 어떤 무더기에서 돌 \(s_3\)개를 제거하고, 이런 식으로 계속된다.
- 일반적으로, \(i\)번째 차례에 제거한 돌의 개수 \(s_i\)는 \(s_{i+1}\)을 나누어야 한다.
자신의 차례에 돌을 제거할 수 없는 소가 먼저 지게 된다.
베시가 승리를 보장하기 위해 첫 차례에 돌을 제거할 수 있는 방법의 수를 계산하라 (즉, 엘시가 어떤 선택을 하더라도 베시가 이기는 전략이 존재하도록 하는 방법의 수). 제거하는 돌의 개수가 다르거나 돌을 제거하는 무더기가 다르면 서로 다른 방법으로 간주한다.
문제 제공: Benjamin Qi
채점 방식
- 테스트 케이스 3-5는 \(N=2\)를 만족한다.
- 테스트 케이스 6-10은 \(N,a_i\le 100\)을 만족한다.
- 테스트 케이스 11-20은 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(a_1,\ldots,a_N\)이 주어진다.
베시가 승리를 보장하기 위해 첫 차례에 돌을 제거할 수 있는 방법의 수를 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.
1
74Bessie wins if she removes \(4\), \(5\), \(6\), or \(7\) stones from the only pile. Then
the game terminates immediately.
6
3 2 3 2 3 18Bessie wins if she removes \(2\) or \(3\) stones from any pile. Then the two players
will alternate turns removing the same number of stones, with Bessie making the
last move.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Gold