LCP의 기댓값

시간 제한1.5초메모리 제한256 MB

요약

각 문자가 독립적으로 균등하게 생성되는 n개의 무한 이진 문자열에서 가장 긴 공통 접두사의 기댓값을 구해 분수 형태로 1e9+7로 나눈 값을 출력한다.

난이도: 어려움10점 중 8점
유형: 확률, 조합론, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

0과 1로만 이루어진 무한 이진 문자열 $n$ 개 $s_1, s_2, \ldots, s_n$ 을 생각하자. 각 문자열의 모든 문자는 서로 독립적으로 균등하게 무작위로 생성된다. $f(s_1, s_2, \ldots, s_n) = \max_{1 \le i < j \le n} LCP(s_i, s_j)$ 로 정의하자. 여기서 $LCP$ 는 두 문자열의 최장 공통 접두사의 길이이다. $f(s_1, s_2, \ldots, s_n)$ 의 기댓값을 구하시오.

입력

첫째 줄에 정수 $n$ 이 주어진다. ( $2 \le n \le 10^4$ )

출력

답을 기약분수 $P / Q$ 로 나타낼 수 있다고 하자. $P \cdot Q^{-1} \bmod (10^9 + 7)$ 을 출력하시오. $Q \bmod (10^9 + 7) \neq 0$ 임이 보장된다.

힌트

기댓값은 항상 유한하다. 즉, $\mathtt{E}f(s_1, \ldots, s_n) < \infty$ 이다.

두 번째 예제에서 답은 $\frac{7}{3}$ 이다.

예제2

예제 1
입력
```
2
```
예상 출력
```
1
```
예제 2
입력
```
3
```
예상 출력
```
333333338
```