CF1205E Expected Value Again

You are given integers $ n $ , $ k $ . Let's consider the alphabet consisting of $ k $ different elements. Let beauty $ f(s) $ of the string $ s $ be the number of indexes $ i $ , $ 1\le i

N/A

N/A

In the first example, there are $ 9 $ words of length $ 2 $ in alphabet of size $ 3 $ — $ aa $ , $ ab $ , $ ac $ , $ ba $ , $ bb $ , $ bc $ , $ ca $ , $ cb $ , $ cc $ . $ 3 $ of them have beauty $ 1 $ and $ 6 $ of them have beauty $ 0 $ , so the average value is $ \frac{1}{3} $ . In the third example, there is only one such word, and it has beauty $ 99 $ , so the average value is $ 99^2 $ .