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


FOMBRO - Editorial



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




Dynamic programming and basic mathematics.


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$$


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


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.
          betdp[N/2] = 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.


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

asked 10 Feb '15, 00:35

amitpandeykgp's gravatar image

accept rate: 0%

edited 11 Feb '16, 19:13

admin's gravatar image

0★admin ♦♦

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

rotozoom's gravatar image

accept rate: 0%

edited 16 Feb '15, 06:54

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:

(19 Feb '15, 12:26) gvaibhav217★

@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) chandan7212★

Access to the source codes denied on the links given.


answered 16 Feb '15, 00:15

sahil2305dua's gravatar image

accept rate: 0%

Will be updated in few minutes.

(16 Feb '15, 00:20) amitpandeykgp4★

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

k0stia's gravatar image

accept rate: 0%

Are you interested in segment tree?

(16 Feb '15, 13:07) amitpandeykgp4★

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

shubham011's gravatar image

accept rate: 0%

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

(17 Feb '15, 15:45) amitpandeykgp4★

@gvaibhav21 awesome solution.


answered 19 Feb '15, 23:12

nivin's gravatar image

accept rate: 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

sjnonweb's gravatar image

accept rate: 0%

For example if N=5,r=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) rahul_nexus2★

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

prateekjjw001's gravatar image

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) amitpandeykgp4★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 10 Feb '15, 00:35

question was seen: 3,283 times

last updated: 11 Feb '16, 19:13