[Medium] StrangeDictionary2

단어의 개수가 16개 이하이므로 단어의 집합을 bitmask 로 나타내어 해결하는 것을 생각해볼 수 있다. 단어의 집합 S가 있을 때 이 중에서 w[i] 가 첫번째에 위치하게 될 확률은 어떻게 될까? 만약 어떤 j에 대해 모든 단어의 j번째 문자가 같다면 j를 permutation 의 어느 위치에 넣어도 정렬 결과가 같다. 따라서 그 j번째 문자를 빼도 확률이 같다. 이제 이런 위치의 문자들을 전부 제거한 상태를 가정하자. 아무 j나 골라서 permutation 의 맨 처음에 놔두면 상태는 다음과 같이 나뉘어진다. 1) w[i][j] 가 모든 j번째 문자 중 제일 작은 문자일 때 j번째 문자가 w[i][j] 보다 큰 단어들은 무조건 정렬 순서가 w[i]의 뒤에 오게된다. 이제부터는 j번째 문자가 w[i][j]와 같은 단어들만 신경쓰면 된다. 그 단어들의 집합을 T라고 하자. 우선, 무조건 T는 S의 진부분집합이 되고, T에 있는 단어들은 모두 j번째 문자가 같으므로 j번째 문자를 빼고 생각할 수 있다. (즉, j는 두번 다시 permutation에 들어갈 일이 없다) 따라서 처음에 생각했던 문제와 정확히 같은 꼴의 부분문제가 된다. 2) w[i][j] 보다 작은 j번째 문자가 존재할 때 무슨 수를 써도 w[i]를 정렬 순서의 맨 처음에 넣을 방법이 존재하지 않는다. 1)에 의해 부분문제 관계가 성립하는 것을 알 수 있고 이로부터 다음과 같은 DP를 생각할 수 있다. Di[S] = 단어의 집합 S가 있을 때, 이 중에서 w[i]가 첫번째에 위치하게 될 확률 = sum( Di[T] ) / C ( 모든 j에 대해 1)에 해당하는 진부분집합 T ) ( C = 모두 같은 문자인 위치를 제거하고 남은 위치의 수 ) Di[P] = 0 , if w[i] is not in P Di[{w[i]}] = 1 이제 이 DP를 이용하면 답을 하나하나 계산할 수 있다. 하지만 이걸 그냥 이대로 돌리면 시간복잡도는 O(N * 2^N * L * N) 이 되어 시간안에 해결할 수 없다. w[i]가 결정된 상태에서, 각 위치 j에 대해 j번째 문자가 w[i][j]와 같은 단어의 집합 j번째 문자가 w[i][j]보다 작은 단어의 집합 두가지를 미리 계산해두면 DP를 2^N * L 만에 계산할 수 있다. 따라서 시간복잡도가 O(N * 2^N * L) 이 되어 시간내에 해결할 수 있게 된다.