leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1569.cpp (962B)

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 };