【hdu 3689】Infinite monkey theorem(概比值dp+kmp)


  Could you imaging a monkey writing computer programs? Surely monkeys are smart among animals. But their limited intelligence is no match for our human beings. However, there is a theorem about

  monkeys, and it states that monkeys can write everything if given enough time.

  The theorem is called “Infinite monkey theorem”. It states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, which of course includes the programs you are about to write (All

  computer programs can be represented as text, right?).

  It’s very easy to prove this theorem. A little calculation will show you that if the monkey types for an infinite length of time the probability that the output contains a given text will approach 100%.

  However, the time used is too long to be physically reasonable. The monkey will not be able to produce any useful programs even if it types until the death of the universe. To verify this and ensure that our human beings are not replaceable by monkeys, you

  are to calculate the probability that a monkey will get things right.