백준 8916 : 이진 검색 트리 c++

https://www.acmicpc.net/problem/8916

8916번: 이진 검색 트리

설명
1. 주어진 입력을 트리로 만든다면 가장 앞의 숫자는 반드시 루트가 된다.
2. 왼쪽 서브트리와 오른쪽 서브트리의 입력순서는 서로 영향을 주지 않는다.
3. 해당 규칙은 서브트리에도 똑같이 적용된다.
4. 현재 트리의 원소의 개수를 n, 왼쪽 서브트리에서 배치할 수 있는 경우의 수 = left , 오른쪽 서브 트리에서 배치할 수 있는 경우의 수 = right, 왼쪽 서브트리의 원소 개수를 l라고 하면 현재 트리에서 배치할 수 있는 경우의 수는
n-1 C l * left * right

5. 재귀적으로 서브트리를 계속 만들어서 경우의 수를 구한다.

#include<bits/stdc++.h>

#include<iostream>


#define MAX 1000000007
#define INF 2000000000
#define MOD 9999991 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 0, 0, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, -1, 0, 0 };

/*
int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };
*/
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

ll com[21][21];
void MakeCombi() {
    for (int i = 1; i <= 20; i++) 
        com[i][0] = 1;

    com[1][0] = com[1][1] = 1;
    for (int i = 2; i <= 20; i++) {
        for (int j = 1; j <= i; j++) {
            com[i][j] = (com[i - 1][j] + com[i - 1][j - 1]) % MOD;
       }
    }

}

ll func(vector<ll> tree) {
    ll len = tree.size();
    if (len <= 2) return 1;
    vector<ll> lv;
    vector<ll> rv;
    ll root = tree.front();
    for (int i = 1; i < tree.size(); i++) {
        if (root > tree[i])
            rv.push_back(tree[i]);
        else
            lv.push_back(tree[i]);
    }
    ll l = func(lv);
    ll r = func(rv);
    return com[len - 1][lv.size()] * l % MOD * r % MOD;
}
int main() {
    init();
    MakeCombi();
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<ll> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        cout << func(v)<<"\n";
    }
}