I could not get Accepted for this problem during contest time, but after contest, after some changes in my code, I could get Accepted for this problem in 9.8 secs! which is too much.
P = population
Q = Sum of populations
C = child[root][child_index]
Solve(root, child_index, x = Q[0..child_index-1]) = Solve(root, child_index+1, x + P[C]) * Solve(C, 0, 0) * Choose(P[C], P[root] - x - 1)
Is there some better way? or you implemented Choose function nicely (which is the main overload of my approach ? )
I don't actually understand what your code means.
But I can tell you I broke the problem down to a simple mathematical equation. The challenge then is evaluating it fast (it includes a factorial).
My final (for now) solution is in O(n) for each test case, but it requires some calculations involving prime numbers in advance. Anyway, reading the input is the bottleneck.
Here is some explanation about my approach:
First, I make a tree in which there is an edge a->b if a is father of b. There are some nodes that don't have father, so I add a super node which is the father of all father-less nodes.
When I want to find the answer for a tree which has A as root, The answer is:
solve(child1) * solve(child2) * solve(child3) * ... * solve(childn) * n! / (count[child1]! * count[child2]! * count[child3]! ... * count[childn]!)
The Solve function I described in the post above is some modified form of this solve function, which does the same operations.
During the contest, I missed that nice observation at which Erik hinted above, but I got accepted by implementing the choose function nicely. You can do this as follows:
* Calculate all primes.
* Make a function f(n,p) that calculates how many times a prime p will appear in n!
* To get choose(n,x_1,x_2,...,x_k) loop over each prime. A prime will appear exactly f(n,p)-sum(f(x_i,p),i=1..k) times in choose(n,x_1,x_2,...,x_k).
What I did during the contest was a little bit different, but also worked:
* If k>2, define a=sum(x_i,i=1..k/2) and b=sum(x_i,i=k/2+1..k), then choose(n,x_1,x_2,...,x_k)=choose(n,a,b)*choose(a,x_1,...x_(k/2))*choose(b,x_(k/2+1),...x_k)
The following was my first attempt, but timed out:
* If k>2, then choose(n,x_1,x_2,...,x_k)=choose(n,x_1,n-x_1)*choose(n-x_1,x_2,....x_k)
krijger wrote:The following was my first attempt, but timed out:
* If k>2, then choose(n,x_1,x_2,...,x_k)=choose(n,x_1,n-x_1)*choose(n-x_1,x_2,....x_k)
That's what I used.
I have additionally precomputed a table with factorials and their inverses modulo 1000000007 (which is a prime), so computing choose(n, x_1, n-x_1) in my solution needed just a few multiplications and divisions.
You can use the extended euclidean algorithm to find the inverse.
If you figured out the formulas, you will notice that you need to do division, so instead of doing the divisions, you can multiply by the inverse.
)
I got it