Question Explanation
The path is split into 3 subpaths (0,0)—>(t,S-1)—>(t,S)—>(P,Q)
Ans is the sum of (number of ways to go from (0,0) to (t,S-1)) * (number of ways to go from (t,S) to (P,Q)) on all possible values of t.
CASE 1:-
R=S=0.Lets consider case 1 where R=S=0 i.e rectangle is intact .to reach the bottom-right corner. The student needs to move right P times and move down Q times .The order of moves doesn’t matter.
The number of ways to go from (0,0) to (P,Q) is :-
C(P+Q,P)=(P+Q)! /(P!*Q!)
Note:- C(P+Q,P)=C(P+Q,Q)
Calculating C(P+Q,P)
Since we have to calculate the ans modulo i.e MOD=1,000,000,007 the above form has to be rewritten to C(P+Q,Q)=(P+Q)!*P!-1 *Q!-1 )mod MOD.Here,x-1 modular multiplicative inverse of x modulo MOD. Since, MOD is a prime number,we can calculate using Fermat Little Theorem x-1 =xMOD-2(mod MOD).We can calculate xMOD-2 in O(log MOD) time using exponentiation by squaring .Just becoz we canj use factorial many times in the solution ,we can precompute all factorial and their inverses (modulo MOD) for all integers from 0 through 8,00,000 inclusive.
p[0]=ip[0]=1
for(i=1;i<=8,00,000);i++)
p[i]=(i*p[i-1])mod MOD
ip[i]=(p[i]MOD-2)mod MOD
The function C(X,Y) can be calculated in constant time as follows.For convenience,we also introduce function ways (P,Q) that returns the number of ways the student can reach the bottom- right corner of an P*Q intact rectangle.
function C(X,Y)
return (p[X]*ip[X-Y]*ip[Y])mod MOD
function ways (P,Q)
return C(P+Q,Q)
CASE 2:-
R,S > 0.
(0,0) R
S
Q
P
Assume the top left corner (0,0) and bottom right corner is (P,Q).
We can split the student’s journey in 3 phases :-
Phase 1: The student moves from top left corner to point (t,S-1).
Phase 2:The student moves down from point (t,S-1) to point (t,S).
(0,0)
t
Phase 3:The student finally moves to (P,Q).
Solution:
#include
#define MAX 800004
#define MOD 1000000007
long long power(long long n,int m);
long long int fact[MAX],ifact[MAX];
void preProcess()
{
fact[0]=1;
ifact[0]=1;
int i;
for(i=1;i1;i--)
ifact[i-1] = ifact[i]*i%MOD;
}
long long int comb(int a,int b)
{
return (((fact[a]*ifact[b])%MOD)*ifact[a-b])%MOD;
}
long long power(long long n,int m)
{
if(m==0)
return 1;
long long x=power(n,m/2);
if(m%2==0)
return (x*x)%MOD;
else
return (((x*x)%MOD)*n)%MOD;
}
int main()
{
preProcess();
int t;
scanf("%d",&t);
while(t--)
{
int m,n,a,b,i,j,k;
scanf("%d%d%d%d",&n,&m,&a,&b);
long long int ans=0;
for(i=0;i<=n-a;i++)
{
ans+=((comb(b-1+i,b-1)*comb(m+n-b-i,m-b))%MOD);
ans%=MOD;
}
printf("%lld\n",ans);
}
return 0;
}