24683번 - I와 l

알파벳의 대소문자 중에서 대문자 I와 소문자 l은, 글꼴에 따라 생긴 것이 비슷하여 잘 구분이 안 되기도 한다. 이는 때때로 유머의 소재로 쓰이기도 하는데, 예를 들면 2020년 3월 28일에 열린 구데기컵의 3개의 디비전 중 5시간짜리 디비전의 이름인 "진짜 최종 구데기컵: ReguIar Division"에서 ReguIar의 다섯 번째 글자는 소문자 l이 아닌 대문자 I였다. Baekjoon Online Judge의 문제 지문의 기본 폰트인 (font)에서 I와 l을 구분할 방법은 길이다. 두 문자를 붙여놓은 Il을 보면, l이 I보다 조금 더 길다는 것을 알 수 있다. 하지만 이렇게 구분할 수 있다고 해도, IlIllIIllI와 같은 문자열은 기억하는데 많은 시간이 걸린다. 그렇기 때문에 본인의 아이디를 쉽게 노출하고 싶지 않은 사람들이 I와 l을 적절히 섞어서 아이디를 만들기도 한다.

I와 l로 된 아이디들을 관찰하던 실버는 문득, 이러한 문자열들의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)의 길이의 기댓값은 어떻게 될지 궁금해졌다. 최장 공통 부분 수열은, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 수열이다. 문자열 $X, Y$에 대해 $X$와 $Y$의 LCS의 길이를 $LCS(X, Y)$라 하자. 여러분은 길이 $n$인 문자열 $S$가 주어졌을 때, I와 l로 이루어진 길이 $m$인 문자열들의 집합(regex 기준 [Il]{m})에서 임의로 뽑은 문자열 $T$에 대해 $LCS(S, T)$의 기댓값을 구해야 한다.

첫 번째 줄에 $n, m$이 주어진다.

두 번째 줄에 I와 l로만 이루어진 길이 $n$의 문자열 $S$가 주어진다.

첫 번째 줄에 문제의 정답을 기약분수 a/b 형태로 출력한다.

• $1 \le n \le 20$
• $1 \le m \le 50$