leetcode

0 class Solution {

1 vector<vector<long long>> table;

2 const int MOD = 1E9 + 7;

3

4 void generate(int numRows) {

5 table.resize(numRows);

6 table[0] = {1};

7 for (int i = 1; i < numRows; i++) {

8 table[i] = vector<long long>(i + 1);

9 table[i][0] = table[i][i] = 1;

10 for (int j = 1; j < i; j++) {

11 table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % MOD;

12 }

13 }

14 }

15

16 long long rec(const vector<int> &nums) {

17 int n = nums.size();

18 if (n <= 2) return 1;

19

20 vector<int> l, r;

21 for (int i = 1; i < n; i++) {

22 (nums[i] < nums.front() ? l : r).push_back(nums[i]);

23 }

24

25 long long lr = rec(l) % MOD, rr = rec(r) % MOD;

26 return (((table[n - 1][l.size()] * lr) % MOD) * rr) % MOD;

27 }

28

29 public:

30 int numOfWays(vector<int> &nums) {

31 generate(nums.size() + 1);

32 return rec(nums) % MOD - 1;

33 }

34 };