 # WEBG01 - Editorial

Author: Vivek Kumar Mishra
Tester: Vivek Kumar Mishra
Editorialist: Vivek Kumar Mishra

EASY

Discrete Math

# PROBLEM:

We have to find the number of feasible paths.

# QUICK EXPLANATION:

The answer to this Question will be the Nth Catalan Number.

# EXPLANATION:

The key observation is that Spider man can never cross the diagonal points and go to the upper Half. You may refer This Link to find out about Catalan Numbers, and how they are applicable in this Question

# SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;

int catalan(int n)
{
long long cat[n+1];
memset(cat,0,sizeof(cat));
cat=1;
for(int i=1; i<=n; ++i)
{
for(int j=0; j<i; ++j)
{
cat[i] = ((cat[i]%M) + (((cat[j]%M) * (cat[i - 1 - j]%M))%M))%M;
}
}
return cat[n];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.in”, “r”, stdin);
freopen(“output.out”, “w”, stdout);
#endif
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;
cout << catalan(n) << ‘\n’;
}
return 0;
}