짜잔, 사실 속으신 거에요!
우선, D-index를 계산하는 데에는 사실 O(M^N) 이 걸리지 않습니다.
D-index의 set size가 1인 경우만 예외로 두면, 적절히 숫자를 선택해서 어떤 range에 구멍이 뚫린 모양의 D-index를 얻을 수 있습니다.
따라서, D-index를 O(MN log N) 과 유사한 속도로 구할 수 있을 것입니다. (자세한 증명은 되어있지 않습니다!) 싸우실래요
D-index를 게임 내에서 구하는 방법을 정의했으니, D-index의 xorsum 연산 (sprague grundy theorem을 적용시키기 위해서) 또한 생각해 봅시다.
마찬가지로, 모든 Game-state의 D-index의 모든 combination을 구해서, 이 combination들의 xor 값들을 set에 넣는 것으로 새로운 D-index를 구할 수 있습니다. 이 또한 O(MN log N)과 비슷한 시간 복잡도로 풀 수 있을 것입니다. (이 역시, 자세한 증명은 되어있지 않습니다.)
이제 D-index를 구하는 방법과 합치는 방법을 구했으니, sprague-grundy theorem을 적용시켜, 어떠한 게임의 합집합도 이기거나 비기는지, 지거나 비기는지를 구할 수 있습니다!
여기서 끝... 이라고 말하면 좋겠지만,
그래서 게임이 선형이 아닌데 D-index를 어떻게 채우죠?
다음 시간에...
'PS' 카테고리의 다른 글
| Solved.ac Grand Arena 후기 (?) (0) | 2023.08.06 |
|---|---|
| Dhyang's method (2.5) 이게 이미 있었네 (0) | 2023.08.02 |
| Dhyang's method (1) 그런디 말입니다... (1) | 2023.06.12 |
| BOJ 27077 16강과 쿼리 (0) | 2023.01.04 |
| 14등 어케함 (0) | 2022.10.05 |