{"raw_statement":[{"iden":"statement","content":"Two boys Gena and Petya wrote on two strips of paper the same string s that consisted of lowercase Latin letters. Then each boy took one strip, cut it into small pieces so that each piece contained exactly one letter and put all pieces into his pocket. After that Gena and Petya repeated the following procedure until their pockets became empty: they took one piece from their pockets and rejoiced if the letters on these pieces were equal.\n\nDetermine the expected number of times the boys rejoiced during this process.\n\nThe input contains the only string s which was initially written on Gena's and Petya's strips. The string has length between 1 and 200000, inclusively, and consists of lowercase Latin letters.\n\nOutput the only real number — the expected number of times Gena and Petya rejoiced during their business. The absolute or relative error of the answer should not exceed 10 - 9.\n\n"},{"iden":"input","content":"The input contains the only string s which was initially written on Gena's and Petya's strips. The string has length between 1 and 200000, inclusively, and consists of lowercase Latin letters."},{"iden":"output","content":"Output the only real number — the expected number of times Gena and Petya rejoiced during their business. The absolute or relative error of the answer should not exceed 10 - 9."},{"iden":"examples","content":"InputabcOutput1.000000000000000InputzzzOutput3.000000000000000"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n $, where $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nLet $ X $ be the random variable denoting the number of times Gena and Petya draw the same letter during the process, where each independently permutes their $ n $ letter pieces uniformly at random and draws them one-by-one in order.\n\n**Objective**  \nCompute $ \\mathbb{E}[X] $, the expected number of matches between the two random permutations of $ s $.\n\n**Key Insight**  \nFor each position $ i \\in \\{1, \\dots, n\\} $, define indicator random variable:  \n$$\nX_i = \\begin{cases}\n1 & \\text{if the } i\\text{-th drawn letters from Gena and Petya are equal} \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$  \nThen $ X = \\sum_{i=1}^n X_i $, and by linearity of expectation:  \n$$\n\\mathbb{E}[X] = \\sum_{i=1}^n \\mathbb{E}[X_i]\n$$\n\nFor each $ i $, $ \\mathbb{E}[X_i] = \\mathbb{P}(\\text{Gena's } i\\text{-th letter} = \\text{Petya's } i\\text{-th letter}) $\n\nSince both permutations are uniform and independent, for a fixed letter $ c $ appearing $ f_c $ times in $ s $, the probability that both draw $ c $ at position $ i $ is:  \n$$\n\\sum_{c \\in \\Sigma} \\left( \\frac{f_c}{n} \\cdot \\frac{f_c}{n} \\right) = \\sum_{c \\in \\Sigma} \\left( \\frac{f_c}{n} \\right)^2\n$$\n\nThus:  \n$$\n\\mathbb{E}[X] = n \\cdot \\sum_{c \\in \\Sigma} \\left( \\frac{f_c}{n} \\right)^2 = \\sum_{c \\in \\Sigma} \\frac{f_c^2}{n}\n$$\n\n**Final Expression**  \n$$\n\\boxed{\\mathbb{E}[X] = \\frac{1}{n} \\sum_{c \\in \\Sigma} f_c^2}\n$$  \nwhere $ f_c $ is the frequency of character $ c $ in string $ s $, and $ n = |s| $.","simple_statement":"Two boys each have a copy of the same string, cut into single letters. They repeatedly pick one letter at random from their own pockets and rejoice if the letters match. What is the expected number of times they rejoice?","has_page_source":false}