403667: GYM101237 D Short Enough Task
Memory Limit:256 MB
Time Limit:0 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
D. Short Enough Tasktime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Do you like expected values as much as we do? Then this problem and the next one are dedicated to you!
Let us generate a random string using the following algorithm: each of N characters of the random string is equiprobably chosen from the alphabet of size K.
Your task is to calculate the expected number of subpalindromes in such a random string.
InputThe input contains two integers N and K, the length of the string and the size of the alphabet respectively (1 ≤ N, K ≤ 109).
OutputOutput the expected number of subpalindromes. Your answer will be considered correct if its absolute or relative error is less than 10 - 6.
ExamplesInput3 2Output
4.5000000000Note
As you remember, a subpalindrome is a non-empty substring of the original string that can be read identically in both directions.