PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:Simple. PREREQUISITES:Dynamic programming and basic mathematics. PROBLEM:You are given a function f which is defined as: $$f(N) = 1^N 2^{N1}.....N^1$$ Find $$\frac {f(N)}{f(r)f(Nr)} \mod M$$ QUICK EXPLANATION:Let $r = \min(r,Nr)$. There will be three cases: $x \le r$, $r < x \le Nr$ and $Nr < 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,Nr)$ and call $ F(N,r) = \frac {f(N)}{f(r)f(Nr)} $. Case 1$(x \le r)$: Power of $x$ in $f(N)$= $N
x+1$. Case 2$(r < x \le Nr)$: Power of $x$ in $f(N)$= $Nx+1$. Case 3$(Nr < x \le N)$: Power of $x$ in $f(N)$= $Nx+1$. As, there can be large number of queries. We need to do some preprocessing to give results. As, results to first and third case doesn't depend on the value of $r$, we can preprocess them and store.
In case 2, it can be noticed that power of $x$ depends on $r$ and the distance of $r$ and $Nr$ from $N/2$ will be the same. So, we can store multiplication of terms which are equidistance from center in an array. So, that we can get value of $Midr = \prod_{r+1}^{Nr} x$ in constant time.
Case 3 will not depend on the value of $r$, so we can do it similar to case 1.
Finally you can calculate the output easily. See Setter's code for the detailed implementation. Second case i.e. calculating $\prod_{r+1}^{Nr} 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. asked 10 Feb '15, 00:35

I've solved with another approach, no segment tree is needed, just math. answered 16 Feb '15, 06:52
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: (n1) * (n2)^k1 * (n3)^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)

Access to the source codes denied on the links given. answered 16 Feb '15, 00:15

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

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
