My solution is like this:

Code: Select all

```
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)
```

**Moderator:** Board moderators

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.

My solution is like this:
Is there some better way? or you implemented Choose function nicely (which is the main overload of my approach ? )

My solution is like this:

Code: Select all

```
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)
```

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.

Cu, Erik

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.

* 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)

That's what I used.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)

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.