Project Euler #151: Paper sheets of standard sizes: an expected-value problem.

  • + 0 comments

    The order of the output is determined by the value of the state which is the order of the recurence calls. The order of the output for N = 4 for the first few configuration states is:

    0 0 0 0: 0, 0 0 0 1: 1, 0 0 0 2: 1, 0 0 0 3: 1, 0 0 0 4: 1, 0 0 1 0: 2, 0 0 1 1: 500000005, 0 0 1 2: 333333337, 0 0 1 3: 250000003, 0 0 2 0: 500000005, 0 0 2 1: 388888893

    To beat all test cases memoization must be used. Moreover we can cache modulo inverse as the biggest one is mod inverse 64.