[Medium] DengklekBuildingRoads

간선을 추가할 정점 쌍을 볼 때, 보는 순서를 정해주자. (1, 2) (1, 3), (2, 3) (1, 4), (2, 4), (3, 4) ... (i-K, i), (i-K+1, i), ..., (i-1, i) ... 이런 순서로 보면서 간선을 배정해줄 것이다. 현재 내가 정점 쌍 (x, i) 에 간선을 놓고 있는 중이라고 해보자. (i-K <= x < i) 이 때 각 정점의 차수가 홀수인지 짝수인지를 관리해야하는데 구체적으로는 i-K번 정점부터 i번 정점까지만 정보를 갖고 있으면 된다. 1번 ~ i-K-1번 정점에는 전혀 영향을 끼칠 수 없기 때문이다. i번에서 간선을 놓는 것이 다 끝나고 i+1번으로 넘어갈 때 i-K번 정점의 parity가 짝수가 되는 상태만 다음으로 넘겨주면 된다. 이를 통해 다음과 같은 DP를 생각할 수 있다. D[i][j][k][bit] = 처음부터 (i-(j+1), i) 까지 총 k개의 간선을 설치하는 경우 bit는 i-K번 정점부터 i번 정점까지의 차수의 parity 들 1) 정점 쌍 (i-(j+1), i) 에 간선을 놓지 않는 경우 1-1) j == K-1 && bit[0] == 0 D[i-1][0][k][bit>>1] 1-2) j < K-1 D[i][j+1][k][bit] 2) 정점 쌍 (i-j+1, i) 에 간선을 한개 추가하는 경우 D[i][j][k-1][bit^(1<<(j+1))^(1<<0)] 답은 D[N][0][M][0] 이다.