Sort 7 Discussions, By:
Please Login in order to post a 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?
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 =  +  * N
for n in xrange(N+1):
for m in xrange(1, 61):
if n + m > N:
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  +  * 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.
 +  * 60
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.
what is modulo 10^9+9 how to represent answer in that format
I am wondering why it is 10^9+9, which is always 10^9+7 in other questions.