# Project Euler #109: Darts

# Project Euler #109: Darts

+ 1 comment "There are exactly 14 distinct ways to checkout on a score of 6"... There seems to be more. For example:

s1 s1 s1 s1 d1 s1 s1 s2 d1 s2 s1 s1 d1 s1 s2 s1 d1 s1 s1 d1 d1 d1 s1 s1 d1 s1 d1 s1 d1

These are not included in the list. Which rules crossed them out?

+ 1 comment The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and

`MemoryError`

from #9 onwards. If you're interested, here is part of my code snippet:mod = int(1e9) + 9 darts = [1] + [0] * N for n in xrange(N+1): for m in xrange(1, 61): if n + m > N: break darts[n+m] += darts[n] * one_dart[m] darts[n+m] %= mod

**EDIT**: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector`[1] + [0] * 60`

. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.

+ 1 comment Can please someone suggest an idea for less than O(N) solution to deal with test cases 9 and above.

I assume that there should be analytic formula for coefficients of series expansion of generating function just can't find one.

+ 0 comments what is modulo 10^9+9 how to represent answer in that format

+ 1 comment I am wondering why it is 10^9+9, which is always 10^9+7 in other questions.

Sort 7 Discussions, By:

Please Login in order to post a comment