PROBLEM LINK:
Author: Vivek Kumar Mishra
Tester: Vivek Kumar Mishra
Editorialist: Vivek Kumar Mishra
DIFFICULTY:
EASY
PREREQUISITES:
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[0]=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;
}