commit de1096dc2000befc3a2c37e4bc483d2db50c3dcc parent 2cf6f4cf29eb000619b440134066739353494bf4 Author: Dimitrije Dobrota <mail@dimitrijedobrota.com> Date: Fri, 16 Jun 2023 15:09:08 +0200 Daily Problem Diffstat:
| A | Problems/1569.cpp | | | 35 | +++++++++++++++++++++++++++++++++++ |
| M | README.md | | | 1 | + |
2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/1569.cpp b/Problems/1569.cpp @@ -0,0 +1,35 @@ +class Solution { + vector<vector<long long>> table; + const int MOD = 1E9 + 7; + + void generate(int numRows) { + table.resize(numRows); + table[0] = {1}; + for (int i = 1; i < numRows; i++) { + table[i] = vector<long long>(i + 1); + table[i][0] = table[i][i] = 1; + for (int j = 1; j < i; j++) { + table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % MOD; + } + } + } + + long long rec(const vector<int> &nums) { + int n = nums.size(); + if (n <= 2) return 1; + + vector<int> l, r; + for (int i = 1; i < n; i++) { + (nums[i] < nums.front() ? l : r).push_back(nums[i]); + } + + long long lr = rec(l) % MOD, rr = rec(r) % MOD; + return (((table[n - 1][l.size()] * lr) % MOD) * rr) % MOD; + } + +public: + int numOfWays(vector<int> &nums) { + generate(nums.size() + 1); + return rec(nums) % MOD - 1; + } +}; diff --git a/README.md b/README.md @@ -482,6 +482,7 @@ for solving problems. | 1547 | Hard | [Minimum Cost to Cut a Stick](Problems/1547.cpp) | | 1557 | Medium | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp) | | 1567 | Medium | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp) | +| 1569 | Hard | [Number of Ways to Reorder Array to Get Same BST](Problems/1569.cpp) | | 1572 | Easy | [Matrix Diagonal Sum](Problems/1572.cpp) | | 1579 | Hard | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp) | | 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |