PROBLEM LINK:
Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey
DIFFICULTY:
Simple.
PREREQUISITES:
Dynamic programming and basic mathematics.
PROBLEM:
You are given a function f which is defined as:
Find
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
(http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp) 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](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:
Setter's solution can be found [here](http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp).
Tester's solution can be found [here](http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp).
here’s my code, its a little simpler: