Count All Valid Pickup and Delivery Options

hard math dp

Problem

Given n orders, each consisting of a pickup and a corresponding delivery, count the number of valid orderings such that delivery(i) is always after pickup(i). Return the answer mod 10^9 + 7.

Inputn = 2

Output6

P1 P2 D1 D2, P1 P2 D2 D1, P1 D1 P2 D2, P2 P1 D1 D2, P2 P1 D2 D1, P2 D2 P1 D1.

def count_orders(n):
    MOD = 10**9 + 7
    ans = 1
    for k in range(1, n + 1):
        ans = ans * k * (2 * k - 1) % MOD
    return ans

function countOrders(n) {
  const MOD = 1_000_000_007n;
  let ans = 1n;
  for (let k = 1n; k <= BigInt(n); k++) {
    ans = ans * k % MOD * (2n * k - 1n) % MOD;
  }
  return Number(ans);
}

class Solution {
    public int countOrders(int n) {
        long ans = 1, MOD = 1_000_000_007L;
        for (long k = 1; k <= n; k++) ans = ans * k % MOD * (2 * k - 1) % MOD;
        return (int) ans;
    }
}

int countOrders(int n) {
    long long ans = 1, MOD = 1000000007LL;
    for (long long k = 1; k <= n; k++) ans = ans * k % MOD * (2 * k - 1) % MOD;
    return (int) ans;
}

Explanation

We count valid orderings of n pickup/delivery pairs where each pickup comes before its delivery. The answer is a neat product: multiply k·(2k-1) for k from 1 to n.

Think of inserting pairs one at a time. When you add the k-th pair to a sequence that already has 2(k-1) items, there are 2k-1 gaps to place the pickup. The delivery must go after the pickup, and counting those valid spots works out to a factor of k, giving k·(2k-1) new ways.

So the code starts at ans = 1 and multiplies by k * (2k - 1) each step, taking everything mod 1e9 + 7 so the number stays in range.

Example: n = 2. Step k=1 multiplies by 1·1 = 1. Step k=2 multiplies by 2·3 = 6. The result is 6, matching the six listed orderings.

This closed form replaces what would otherwise be a more involved DP, running in a simple linear loop.

Time: O(n) Space: O(1)