전체 오차가 이하이므로 각 항도 를 만족한다. 이고 이므로, 가능한 음정은 부터 까지이다. 이 범위의 정수 개수는 이다.
를 첫 개 항을 정했을 때, 오차의 합이 정확히 이고 마지막 음정 가 인 수열의 개수라고 하자. , 인 상태를 저장한다.
첫 음정은 으로 고정되어 있으므로 첫 항의 오차는 이다. 이면
로 초기화하고, 나머지 상태는 으로 둔다. 이면 가능한 수열이 없으므로 바로 을 출력할 수 있다.
이제 이고 마지막 음정을 로 정한다고 하자. 이번 항의 오차는 이므로, 앞의 개 항에서 사용한 오차는 여야 한다. 이전 음정 는 를 만족해야 하므로 일 때
이다. 인 상태의 값은 이다.
순서로 각 오차 와 마지막 음정 를 순회하고, 위 구간의 를 직접 순회하여 더하면 된다. 모든 덧셈은 로 나눈 나머지로 계산한다.
최종 답은
이다. 오차가 정확히 인 상태만 세는 것이 아니라, 이하인 모든 상태를 더해야 한다.
상태는 개이고, 각 상태에서 이전 음정을 최대 개 확인한다. 따라서 시간 복잡도는
이다. 이는 원소 개수 × 음정 범위 × 총 오차 범위 × 인접 음정 차이 범위에 해당한다. 주어진 제한에서는 이 전이를 직접 계산할 수 있다.
매 단계는 바로 이전 단계만 사용하므로 배열을 두 층만 저장하면 된다. 공간 복잡도는 이다. 음정 는 배열의 인덱스 에 대응시키면 된다.
증명
첫 항은 으로 유일하게 정해지고 오차는 이다. 따라서 일 때 로 두는 초기화는 길이 인 유효한 수열을 정확히 한 번 센다. 이면 이후 항을 정해도 총 오차를 줄일 수 없으므로 답은 이다.
Solution written by GPT6
이 올바르다고 가정하자. 마지막 음정이 이고 총 오차가 인 유효한 수열에서 마지막 항을 지우면, 오차가 이고 마지막 음정 가 를 만족하는 이전 수열이 남는다.
반대로 이러한 이전 수열에 를 붙이면 인접 음정 차이 조건을 만족하며 총 오차는 정확히 가 된다. 두 과정은 서로 반대이므로 전이는 유효한 수열을 빠짐없이, 중복 없이 센다. 마지막에 인 상태를 모두 더하면 원하는 답을 얻는다.
