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

아이디어

문제는 M이 주어졌을 때 0<N<M을 만족하는 N중 그런디 수가 0인것을 찾으면 된다. dp를 통해 그런디 수를 구하면 시간이 어마어마하게 걸림으로 dp를 이용해서 구할 수 있는 부분은 dp로 구해주고 나머지는 그런디 수의 사이클을 구해서 개수를 유추해주는 방법으로 가야한다. 방법론은 참 간단하지만 구현은 욕나온다

여기서 주의해야하는 점은 사이클이 무조건 첫번째부터 시작하지 않는다는것이다.

정답

import sys

input = sys.stdin.readline
M = int(input().rstrip())
K = int(input().rstrip())
moves = list(map(int,input().split()))

NNN = 300000
NN = 100000
dp = [0] * (NNN+1)
m = 0
for i in range(1,NNN+1):
    for move in moves:
        state = i - move
        if state < 0:
            break
        m |= (1<<dp[state])
    grundy = 0
    while m > 0:
        if m & 1 == 0:
            break
        grundy += 1
        m >>= 1
    dp[i] = grundy
    m = 0
answer = 0
if M < NN:
    for i in range(1,M+1):
        if dp[i] == 0:
            answer+=1
    print(answer)
else:
    for i in range(1,NN+1):
        if dp[i] == 0:
            answer+=1
    length = 1
    for i in range(2,2000):
        is_cycle = True
        for j in range(NN+1,NN + 2001):
            if dp[j] != dp[j + i]:
                is_cycle = False
                break
        if is_cycle:
            length = max(length,i)
    count = 0
    for i in range(NN+1,NN+1+length):
        if dp[i] == 0:
            count+=1
    answer += ((M-NN)//length) * count
    for i in range(NN+1,(NN + ((M-NN)%length))+1):
        if dp[i] == 0:
            answer+=1
    print(answer)