| Codeforces Round 129 (Div. 1) |
|---|
| Закончено |
Маленький Слоник очень любит Фурика и Рубика, с которыми он познакомился в мегаполисе городского типа Кременчуге.
У Маленького Слоника есть две строки a и b одинаковой длины, состоящие только из прописных букв латинского алфавита. Маленький Слоник выбирает пару подстрок одинаковой длины — первую из строки a, вторую из строки b. Выбор происходит случайно равновероятно среди всех возможных пар. Обозначим подстроку строки a через x, а подстроку строки b — через y. Строку x Маленький Слоник отдает Фурику, строку y — Рубику.
Пусть f(x, y) — количество таких позиций i (1 ≤ i ≤ |x|), что xi = yi (где |x| — длина строк x и y, а xi, yi — i-ые символы строк x и y соответственно). Помогите Фурику и Рубику найти математическое ожидание величины f(x, y).
В первой строке задано единственное целое число n (1 ≤ n ≤ 2·105) — длина строк a и b. Во второй строке задана строка a, в третьей — строка b. Строки состоят только из прописных букв латинского алфавита. Длина обеих строк равна n.
В единственной строке выведите вещественное число — ответ на задачу. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не будет превышать 10 - 6.
2
AB
BA
0.400000000
3
AAB
CAA
0.642857143
Пусть задана строка a = a1a2... a|a|, тогда обозначим через |a| длину строки, а через ai — i-й символ строки.
Подстрокой a[l... r] (1 ≤ l ≤ r ≤ |a|) строки a называется строка alal + 1... ar.
Строка a является подстрокой строки b, если существует такая пара целых чисел l и r (1 ≤ l ≤ r ≤ |b|), что b[l... r] = a.
Рассмотрим первый тестовый пример. В первом примере есть 5 возможных пар подстрок: («A», «B»), («A», «A»), («B», «B»), («B», «A»), («AB», «BA»). Для второй и третьей пары знечение f(x, y) равно 1, для остальных — 0. Вероятность выбора каждой пары равна 
, поэтому ответ равен · 0 + · 1 + · 1 + · 0 + · 0 = 
= 0.4.
