301078: CF204C. Little Elephant and Furik and Rubik
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Little Elephant and Furik and Rubik
题意翻译
小象喜欢Furik和Rubik,他在一个小城市Kremenchug遇到了他。 小象有两条长度相等的字符串$a$和$b$,仅由大写英文字母组成。小象选择一对长度相等的子串,第一个来自串a,第二串来自串b。在所有可能的配对之中等概率选择。让我们将a的子字符串表示为x,将b的子字符串表示为y。小象将字符串x交给Furik,字符串y交给Rubik。 让我们定义$F(x,y)$是满足如下条件的位置$i$的数目: $(1 <= i <= |x|)$,同时$x_i = y_i$($|x|$为字符串 X 的长度,$x_i,y_i$是x和y的第i个字符串对应位置的字符) 请帮助Furik和Rubik求出$F(x,y)$的期望. 输入 第一行包含一个整数$n (1 <= n <= 2 \times 10^5)$ ,表示字符串a和b的长度.。第二行包含字符串a,第三行包含字符串b。字符串只包含大写英文字母。两个字符串的长度均等于n。 输出 一行,一个实数,表示问题的答案.你的答案与标准答案的误差不超过$10^{-6}$即被认为正确. 感谢@Maniac丶坚果 提供的翻译题目描述
Little Elephant loves Furik and Rubik, who he met in a small city Kremenchug. The Little Elephant has two strings of equal length $ a $ and $ b $ , consisting only of uppercase English letters. The Little Elephant selects a pair of substrings of equal length — the first one from string $ a $ , the second one from string $ b $ . The choice is equiprobable among all possible pairs. Let's denote the substring of $ a $ as $ x $ , and the substring of $ b $ — as $ y $ . The Little Elephant gives string $ x $ to Furik and string $ y $ — to Rubik. Let's assume that $ f(x,y) $ is the number of such positions of $ i $ ( $ 1<=i<=|x| $ ), that $ x_{i}=y_{i} $ (where $ |x| $ is the length of lines $ x $ and $ y $ , and $ x_{i} $ , $ y_{i} $ are the $ i $ -th characters of strings $ x $ and $ y $ , correspondingly). Help Furik and Rubik find the expected value of $ f(x,y) $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — the length of strings $ a $ and $ b $ . The second line contains string $ a $ , the third line contains string $ b $ . The strings consist of uppercase English letters only. The length of both strings equals $ n $ .
输出格式
On a single line print a real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed $ 10^{-6} $ .
输入输出样例
输入样例 #1
2
AB
BA
输出样例 #1
0.400000000
输入样例 #2
3
AAB
CAA
输出样例 #2
0.642857143