FOMBRO - Editorial

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* = (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* = ((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*= (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

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

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

@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.

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

Will be updated in few minutes.

Are you interested in segment tree?

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

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?

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.