leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1569.cpp (962B)

      1 class Solution {
      2     vector<vector<long long>> table;
      3     const int MOD = 1E9 + 7;
      4 
      5     void generate(int numRows) {
      6         table.resize(numRows);
      7         table[0] = {1};
      8         for (int i = 1; i < numRows; i++) {
      9             table[i] = vector<long long>(i + 1);
     10             table[i][0] = table[i][i] = 1;
     11             for (int j = 1; j < i; j++) {
     12                 table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % MOD;
     13             }
     14         }
     15     }
     16 
     17     long long rec(const vector<int> &nums) {
     18         int n = nums.size();
     19         if (n <= 2) return 1;
     20 
     21         vector<int> l, r;
     22         for (int i = 1; i < n; i++) {
     23             (nums[i] < nums.front() ? l : r).push_back(nums[i]);
     24         }
     25 
     26         long long lr = rec(l) % MOD, rr = rec(r) % MOD;
     27         return (((table[n - 1][l.size()] * lr) % MOD) * rr) % MOD;
     28     }
     29 
     30   public:
     31     int numOfWays(vector<int> &nums) {
     32         generate(nums.size() + 1);
     33         return rec(nums) % MOD - 1;
     34     }
     35 };