You are not logged in. Please login at www.codechef.com to post your questions!

×

# 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[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 code for the detailed implementation.

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 for the more details on segment tree. See tester's code for the implementation of this approach.

# Solutions:

Setter's solution can be found here.
Tester's solution can be found here.

asked 10 Feb '15, 00:35 25911522
accept rate: 0% 19.8k350498541

 3 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 answered 16 Feb '15, 06:52 3★rotozoom 41●2 accept rate: 0% this was EXACTLY my approach!! easy to implement, which helped me to quickly solve 3 questions :D here's my code, its a little simpler: http://www.codechef.com/viewsolution/6283536 (19 Feb '15, 12:26) @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? (22 Feb '15, 23:41)
 0 Access to the source codes denied on the links given. answered 16 Feb '15, 00:15 11●2 accept rate: 0% Will be updated in few minutes. (16 Feb '15, 00:20)
 0 could someone give me list of problems with similar idea which is used in tester's code? thanks in advance! answered 16 Feb '15, 01:39 4★k0stia 41●6 accept rate: 0% Are you interested in segment tree? (16 Feb '15, 13:07)
 0 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 answered 17 Feb '15, 04:16 178●3●7●18 accept rate: 0% I don't think so, check other's code soe might have got accepted. (17 Feb '15, 15:45)
 0 @gvaibhav21 awesome solution. answered 19 Feb '15, 23:12 4★nivin 11●1●3 accept rate: 0%
 0 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. answered 21 Feb '15, 17:50 2★sjnonweb 1 accept rate: 0% For example if N=5,r=2 F(5,2)=(5!4!3!2!)/((3!2!)(2!))=((5!*4!)/2!)= 5^14^23^22^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}. (21 Feb '15, 23:42)
 0 Can someone please explain case 2. The if else statement and the for loop statements. I do not understand the math behind it. answered 23 Feb '15, 00:15 46●2 accept rate: 10% 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. (23 Feb '15, 10:55)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212
×1,191
×139
×109
×4

question asked: 10 Feb '15, 00:35

question was seen: 3,283 times

last updated: 11 Feb '16, 19:13