Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1359.html
1359. Count All Valid Pickup and Delivery Options (Hard)
Given n
orders, each order consist in pickup and delivery services.
Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
Example 2:
Input: n = 2 Output: 6 Explanation: All possible orders: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1). This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
Example 3:
Input: n = 3 Output: 90
Constraints:
1 <= n <= 500
Related Topics:
Math, Dynamic Programming
Solution 1.
Let f(n)
be the answer.
It’s trivial that f(1) = 1
For n = 2
, the single arrangement of f(1)
gives us 3
spots to put P2
.
 If
P2
is put at the first spot,D2
has3
spots to be put.  If
P2
is put at the 2nd spot,D2
has2
spots to be put.  If
P2
is put at the 3rd spot,D2
has1
spot to be put.
So f(2) = 3 + 2 + 1 = 6
or f(2) = (1 + N) * N / 2 * f(1)
where N = 3 = 2 * 2  1
.
By induction, we have f(n) = f(n  1) * (1 + N) * N / 2
where N = 2n  1
// OJ: https://leetcode.com/problems/countallvalidpickupanddeliveryoptions/
// Time: O(N)
// Space: O(1)
typedef long long LL;
class Solution {
public:
int countOrders(int n) {
LL ans = 1, mod = 1e9 + 7;
for (int i = 2; i <= n; ++i) {
LL prev = ans, cnt = 2 * i  1;
ans = ((cnt + 1) * cnt / 2) % mod;
ans = (ans * prev) % mod;
}
return ans;
}
};
Java

class Solution { public int countOrders(int n) { final int MODULO = 1000000007; long count = 1; for (int i = 2; i <= n; i++) { long twice = i * 2 % MODULO; long curCount = twice * (twice  1) / 2 % MODULO; count = (count * curCount) % MODULO; } return (int) count; } }

// OJ: https://leetcode.com/problems/countallvalidpickupanddeliveryoptions/ // Time: O(N) // Space: O(1) typedef long long LL; class Solution { public: int countOrders(int n) { LL ans = 1, mod = 1e9 + 7; for (int i = 2; i <= n; ++i) { LL prev = ans, cnt = 2 * i  1; ans = ((cnt + 1) * cnt / 2) % mod; ans = (ans * prev) % mod; } return ans; } };

print("Todo!")