# FOMBRO - Editorial

Practice

Contest

Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey

Simple.

### PREREQUISITES:

Dynamic programming and basic mathematics.

### PROBLEM:

You are given a function f which is defined as:

f(N) = 1^N 2^{N-1}.....N^1

Find

\frac {f(N)}{f(r)f(N-r)} \mod M

### QUICK EXPLANATION:

Let r = \min(r,N-r). There will be three cases: x \le r, r < x \le N-r and
N-r < x \le N. Calculate power of x in each of the case and multiply them taking modulo M.

### EXPLANATION:

The give problem can be solved using simple dynamic programming approach.

Let r = \min(r,N-r) and call F(N,r) = \frac {f(N)}{f(r)f(N-r)} .

Case 1(x \le r):

Power of x in f(N)= N -x+1.
Power of x in f(r)= r-x+1.
Power of x in f(N-r)= (N-r)-x+1.
Hence, Power of x(\le r) in F(N,r)= (N-x+1) - (r-x+1) - ((N-r)-x+1) = x-1.

Case 2(r < x \le N-r):

Power of x in f(N)= N-x+1.
Power of x in f(r)= 0. as (x > r)
Power of x in f(N-r)= (N-r)-x+1.
Hence, Power of x in F(N,r)= (N-x+1) - ((N-r)-x+1) = r .

Case 3(N-r < x \le N):

Power of x in f(N)= N-x+1.
There will not be any term corresponding to denominator.
Hence, Power of x in F(N,r)= (N-x+1).

As, there can be large number of queries. We need to do some pre-processing to give results.
As, results to first and third case doesnâ€™t depend on the value of r, we can pre-process them and store.

    //Case I : For the given value of r, fordp[r] will store multiplication
of all x corresponding to the first case.
for(int i=1;i<=N/2;i++)
fordp[i] = (fordp[i-1]*binpow(i,i-1,M))%M;


In case 2, it can be noticed that power of x depends on r and the distance of r and N-r from N/2 will be the same. So, we can store multiplication of terms which are equi-distance from center in an array. So, that we can get value of Midr = \prod_{r+1}^{N-r} x in constant time.

     //Case 2 : You can get Midr in O(1) time.
if(N&1)
betdp[N/2] = N/2 +1;
else
betdp[N/2]=1;
for(ll i=N/2-1;i>=1;i--)
betdp[i] = ((ll)((betdp[i+1]*(i+1))%M)*(ll)(N-i))%M;


Case 3 will not depend on the value of r, so we can do it similar to case 1.

    //Case III
for(ll i=1;i<=N/2;i++)
backdp[i]= (backdp[i-1]*binpow(N-i+1,i,M))%M;


Finally you can calculate the output easily. See Setterâ€™s



Second case i.e. calculating $\prod_{r+1}^{N-r} x % M$ can also be done using the segment tree. In the segment tree, a node will store the multiplication of both of the children mod $M$. Refer this wonderful [tutorials](http://letuskode.blogspot.in/2013/01/segtrees.html) for the more details on segment tree. See [tester's code](http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp) for the implementation of this approach.

### Solutions:

Tester's solution can be found [here](http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp).
4 Likes

Will be updated in few minutes.

could someone give me list of problems with similar idea which is used in testerâ€™s code? thanks in advance!

Iâ€™ve solved with another approach, no segment tree is needed, just math.

We can see, that F(n) = n! * (n-1)! * â€¦ * 2!
Lets rmin = min(r, n - r) and rmax = max(r, n - r)

So, answer is (n! * (n - 1)! * â€¦ * 2!) / ((rmin! * (rmin - 1)! * â€¦ * 2!) * (rmax! * (rmax - 1)! * â€¦ *2!))

Letâ€™s make it simpler by removing f(rmax):

(n! * (n - 1)! * â€¦ * (n - rmax + 1)!) / (rmin! * (rmin - 1)! * â€¦ * 2!)

Now we can see that number of the terms in the denominator + 1 equal number of terms in the numerator, so we can separately divide: (n-1)! / rmin!, (n-2)! / (rmin-1)!, â€¦ , (n-rmax+1)! / 2!

Letâ€™s see what we have: (n-1) * (n-2)^k1 * (n-3)^k2 * â€¦ * 5^k2 * 4^k1 * 3

ki depends on rmin.
when rmin == 2, all ki == 1

when rmin == 3, all ki == 2

when rmin == 4, k1 == 2, ki == 3 for each i>2

and so on.

Letâ€™s denote this product X(rmin), so the final answer will be n! * X(rmin) % m.

For each n and m we precalculate X(i) [2 <= i <= n/2] with complexity O(n).

Final answer we get for O(1).

Do not forget to process corner cases separately, when n < 5 or r == n - 1.

Total complexity: O(N).
Solution

3 Likes

Are you interested in segment tree?

I used segment tree for case 2 â€¦ does it take time really more than given limit or its just because of JAVA that it showed TLE

I donâ€™t think so, check otherâ€™s code soe might have got accepted.

this was EXACTLY my approach!! easy to implement, which helped me to quickly solve 3 questions hereâ€™s my code, its a little simpler: http://www.codechef.com/viewsolution/6283536

@gvaibhav21 awesome solution.

The answer directly started with case 1(x<=r). could someone tell me what value is â€śxâ€ť holding here?
Also i really didnâ€™t understood the math behind this question.

For example if N=5,r=2

F(5,2)=(5!*4!*3!*2!)/((*3!2!)(2!))=((5!*4!)/2!)=

5^14^23^2*2^1 = [(5^1) * (4)^2 ] *[(3)^2] *[ (2^1) ]

                   ^              ^         ^
|              |         |
Case 3        Case 2     Case 1


Here x is the the base i.e {5,4,3,2}.

@rotozoom I also tried the same approach during contest, but got stuck on the step where you have mentioned

Letâ€™s see what we have: (n-1) * (n-2)^k1 * (n-3)^k2 * â€¦ * 5^k2 * 4^k1 * 3

I am still unable to understand how this step came.
Could you please elaborate a bit more?

Can someone please explain case 2. The if else statement and the for loop statements. I do not understand the math behind it.

It is basically about whether N is even of odd, and we are taking the multiplication for the range [N/2-x,N/2+x], So In case of N is odd, we have to initialize product by N/2+1.