← 返回题目列表

Codeforces · 204/C

C. 小象和福里克和魔力

中文机器翻译题面 查看原题

小象很喜欢福里克和鲁比克,他们是他在小城市克列缅楚格认识的。

小象有两个长度相等的字符串a和b,仅由大写英文字母组成。小象选择一对长度相等的子串——第一个来自字符串 a,第二个来自字符串 b。在所有可能的对中,选择的概率是相等的。我们将 a 的子串表示为 x,将 b 的子串表示为 y。小象把字符串 x 给了福里克,把字符串 y 给了鲁比克。

假设 f(x, y) 是 i (1 ≤ i ≤ |x|) 的位置数,即 xi = yi(其中 |x| 是 x 和 y 行的长度,xi、yi 分别是字符串 x 和 y 的第 i 个字符)。帮助 Furik 和 Rubik 求 f(x, y) 的期望值。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 字符串 a 和 b 的长度。第二行包含字符串a,第三行包含字符串b。字符串仅由大写英文字母组成。两个字符串的长度都等于n。

输出

在一行上打印一个实数——问题的答案。如果答案的相对误差或绝对误差不超过 10 - 6,则认为答案是正确的。

示例

输入 #1

2
AB
BA

输出 #1

0.400000000

输入 #2

3
AAB
CAA

输出 #2

0.642857143

注意

假设给定字符串 a = a1a2... a|a|,然后将字符串的长度表示为 |a|,将其第 i 个字符表示为 ai。

字符串 a 的子串 a[l... r] (1 ≤ l ≤ r ≤ |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。选择每对的概率等于 $$\frac{1}{5}$$,这就是为什么答案是 $$\frac{1}{5}$$ · 0 + $$\frac{1}{5}$$ · 1 + $$\frac{1}{5}$$ · 1 + $$\frac{1}{5}$$ · 0 + $$\frac{1}{5}$$ · 0 = $$\frac{2}{5}$$ = 0.4。