# PATHWAY - Editorial

Practice

Contest

Author: Niket Agarwal

Tester: Pritish Priyatosh Nayak

Editorialist: Niket Agawal

Easy

# Prerequisites:

Combinatorics, Modular Inverse

# Problem:

Given a set of moves. Find the number of ways to reach from one point to other in a lattice.

# Explanation:

This problem was an extension of the normal lattice path counting problem.
In the original problem, we had to find the number of ways to reach from (0,0) to (x,y). So, consider we had x horizontal arrows and y vertical arrows. All the possible arrangements of the arrows was the answer, which is (x+y)!/(x!y!).

We see that we have to simply count the number of permutations with repeated elements.

For this question, instead of all arrows having the same length, we have different lengths. So, we simply count the frequency of horizontal and vertical moves. Remember not to mix the frequency of horizontal and vertical moves, since they have different arrows.

So, simply the answer would be (N+M)!/Product of(frequency of each move)!

Remember to use a map for counting the frequency since the range lies upto 1e9.

# Solutions:

Setter's/Editorialist's Solution
``````import java.util.*;import java.io.*;import java.math.*;
public class Main
{
static long[]fac;
public static void process()throws IOException
{
long x=nl();
long y=nl();
int n=ni();
int m=ni();
fac=new long[n+m+1];
fac[0]=1l;
for(int i=1;i<=n+m;i++)
fac[i]=(i*fac[i-1])%mod;
long ans=fac[n+m];
HashMap<Integer,Integer>mx=new HashMap<>();
HashMap<Integer,Integer>my=new HashMap<>();
for(int i=0;i<n;i++)
{
int temp=ni();
if(mx.containsKey(temp))
mx.put(temp,mx.get(temp)+1);
else mx.put(temp,1);
}
for(int i=0;i<m;i++)
{
int temp=ni();
if(my.containsKey(temp))
my.put(temp,my.get(temp)+1);
else my.put(temp,1);
}
for(Map.Entry<Integer,Integer>e:mx.entrySet())
ans=(ans*modInv(fac[e.getValue()]))%mod;
for(Map.Entry<Integer,Integer>e:my.entrySet())
ans=(ans*modInv(fac[e.getValue()]))%mod;
pn(ans);
}

static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
int t=1;
// t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static long power(long x,long y)
{
long res=1l;
x%=mod;
while(y>0)
{
if(y%2==1)
res=(res*x)%mod;
y/=2;
x=(x*x)%mod;
}
return res%mod;
}
static long modInv(long n)
{return power(n,mod-2);}
static long mod=(long)1e9+7l;
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
catch (IOException  e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;

int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
int mul(int a, int b, int p = mod){ return (a * (long long)1 * b) % p; }
int powm(int b, int e,int m=mod){int r=1;while(e>0){if(e%2==1)r=(r*b)%m;b=(b*b*1LL)%m;e/=2;}return r%m;}
int divi(int a, int b, int p = mod){ return mul(a,powm(b,p-2,p));}

signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif

int x,y;
cin>>x>>y;
// assert(x>=1&&y>=1&&x<=1e10&&y<=1e10);

int n,m;
cin>>n>>m;
// assert(n>=1&&m>=1&&n<=1e5&&m<=1e5);

int N[n],M[m];
int sumN=0,sumM=0;

map<int,int> mpp1,mpp2;
for (int i = 0; i < n; ++i)
{
cin>>N[i];
sumN+=N[i];
mpp1[N[i]]++;
// assert(N[i]>=1&&N[i]<=1e9);
}
// assert(sumN==x);
for (int i = 0; i < m; ++i)
{
cin>>M[i];
sumM+=M[i];
mpp2[M[i]]++;
// assert(M[i]>=1&&M[i]<=1e9);
}
// assert(sumM==y);

int ans=1;
int fact[n+m+5]={0};
fact[0]=1;
for (int i = 1; i <= n+m; ++i)
{
fact[i] = mul(fact[i-1],i);
}
ans=fact[n+m];

for(auto &[x,y]:mpp1)
{
ans=divi(ans,fact[y]);
}
for(auto &[x,y]:mpp2)
{
ans=divi(ans,fact[y]);
}

cout<<ans;

cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
``````