Author: yashu2040
Tester: pulkit_0110
Editorialist: yashu2040
DIFFICULTY:
MEDIUM.
#EXPLANATION
The key idea is that for any n, you can select the pair having colour n and place the pair in any position such that left parentheses occurs before right parentheses and these position can be calculated in 2nC2 ways.
Now you are left with (n-1) pairs, apply the same logic to remaining pairs.
You can precalculate the answer of each n <= 1e5 and each query can be solved in O(1) time complexity.
Here’s the code :
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll mod = 1000000007;
ll dp[100000+1];
dp[1] = 1;
dp[2] = 6;
for(int i=3; i<=100000; i++) {
dp[i] = ((dp[i-1](2i-1)%mod)*i)%mod;
}
int t = 1;
cin>>t;
while(t–){
int n;
cin>>n;
cout<<dp[n]<<“\n”;
}
}