[Hard] PickAndDelete

문제를 명확하게 바꾸면 다음과 같다. 길이가 N이면서 다음과 같은 성질을 만족하는 수열 X의 개수를 구해라. - X를 오름차순으로 정렬한 수열을 Y라 할 때, Y[i] <= S[i] (1 <= i <= N) 길이가 i일 때의 개수를 good(i) 이라 해보자. 포함배제를 쓰면 쉽게 계산할 수 있다. 먼저, 모든 수는 Y[i] 이하여야 하므로 그걸 만족하는 수열의 개수는 Y[i]^i 개다. 이것들 중에서 Y[k] <= S[k] 를 만족하지 않는 k가 존재하는 수열의 개수를 빼주면 된다. bad(i, j) = k < j 에선 전부 Y[k] <= S[k] 이고, Y[j] > S[j] 인 수열 X의 개수 라고 정의하면 good(i) = Y[i]^i - sum( bad(i, j) , 1 <= j < i ) 가 된다. 이제 bad(i, j) 를 구하는 법을 알아보자. 1 ~ j-1 까지는 조건을 만족하므로 good(j-1) 에서 경우를 가져오면 된다. j에서 처음으로 Y[j] > S[j] 가 되었으므로, 이 뒤엔 오름차순이기만 하면 아무거나 와도 된다. 따라서 j ~ i 를 만드는 경우는 (Y[i]-Y[j])^(i-j+1) 개다. 여기까지 우리는 수열 Y를 만드는 경우의 수를 따졌으므로, 수열 X를 만드는 경우를 따지려면 전체 i개 자리 중 j-1개 자리를 골라 good(j-1) 의 원소들을 배치하고 나머지 자리에 나머지를 배치하는 경우를 곱해주면 된다. 정리하면 다음과 같다. bad(i, j) = good(j-1) * (Y[i]-Y[j])^(i-j+1) * comb(i, j-1) 답은 good(N) 이다. 전체 시간복잡도는 O(n^2 logn)