E1과 E2는 동일한 문제이나 E2의 범위가 더 크다

문제 태그

• 수학
• 통계학

아이디어

1. 기본 개념

• 모자이크의 아름다움 = $(correctness)^2$
  • X = 모자이크 내 모든 팰린드롬 부분 문자열의 개수
  • 목표: $E[X^2]$ 계산하기

2. X를 중심별로 나누기

• 각 팰린드롬은 중심점을 가지고 있음
• $N_c$ = 중심이 c인 팰린드롬의 개수
• $X = \underset{all\ center\ c}{\sum}N_c$ (모든 중심의 팰린드롬 개수를 합침)

3. $E[X^2]$ 계산하기

$X^2$를 전개하면:

$$ X^2 = \left( \underset{c}{\sum} N_c\right)^2 = \underset{c}{\sum} N^2_c + \underset{c\not =d}{\sum} N_cN_d $$

기대값을 취하면:

$$ E[X^2] = \underset{c}{\sum} E[N^2_c] + \underset{c\not =d}{\sum} E[N_cN_d] $$

4. 핵심 아이디어: 독립성

서로 다른 중심 c와 d에 대해 $N_c$와 $N_d$는 독립적이다