Random Walk: Hard version

Revision en1, by Swistakk, 2016-02-15 19:54:11

Hi!
On recent OpenCup — Makoto Soejima Contest 4, problem "Random Walk" was posed. We were requested to determine the expected number of visited cells after n steps of random walk on a plane — in each move from (i, j) we go either to (i+1, j), (i-1, j), (i, j+1) or (i, j-1) — all with prob 1/4. More precisely, we needed to output , where M was some integer. In this problem constraint was n ≤ 5000. Actually, this problem becomes much more interesting if we try to solve it for n ≤ 105 in a reasonable time (assume M = 109 + 7 for simplicity). Can you see the solution (if I'm not mistaken — it exists)?

Tags random, walk, ez, maxflow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Swistakk 2016-02-15 19:54:11 694 Initial revision (published)