Count the Number of Inversions

This problem can be solved efficiently using dynamic programming. The core idea is to build the permutations incrementally by length, from 1 to n. At each step i, we calculate the number of permutations of length i for each possible number of inversions j. The key is the recurrence relation that connects the number of permutations of length i with j inversions to the counts for permutations of length i-1.

1. Pre-process the requirements array into a map for efficient lookups, mapping end_i + 1 (prefix length) to cnt_i.
2. Determine the maximum required inversion count, max_cnt, from the requirements. This will be the size of our DP array.
3. Initialize a DP array, dp, of size max_cnt + 1. dp[j] will store the number of valid permutations of the current length with j inversions. Start with dp[0] = 1 representing one empty permutation with 0 inversions.
4. Iterate i from 1 to n. In each iteration i, we calculate the DP table for permutations of length i based on the table for length i-1.
5. Inside the loop, first compute a prefix sum array ps for the current dp array. ps[j] = (ps[j-1] + dp[j]) % MOD.
6. Create a new_dp array. For each j from 0 to max_cnt, calculate new_dp[j] using the recurrence dp[i][j] = sum_{k=0}^{i-1} dp[i-1][j-k]. This sum is efficiently found using the prefix sum array: ps[j] - ps[j-i] (with modulo arithmetic).
7. After computing new_dp, update dp = new_dp.
8. Check if there is a requirement for length i. If reqMap contains i, let the required count be c. Enforce the constraint by setting dp[j] = 0 for all j != c.
9. After the loop finishes (i.e., i=n), the answer is the value in dp at the index corresponding to the final requirement's count, dp[reqMap.get(n)].

Let dp[i][j] be the number of permutations of [0, 1, ..., i-1] with exactly j inversions. A permutation of length i is formed by taking a permutation of [0, ..., i-2] and inserting the number i-1. Since i-1 is the largest number, inserting it at the k-th position from the end adds k new inversions (0 <= k < i). This leads to the recurrence: dp[i][j] = sum_{k=0}^{i-1} dp[i-1][j-k]. This sum can be optimized using prefix sums.

We can use a 1D DP array and iterate from length 1 to n, updating the counts at each step. After each step i, we apply the constraint from requirements for prefixes of length i, if any, by zeroing out counts for non-matching inversion numbers.

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        int MOD = 1_000_000_007;
        Map<Integer, Integer> reqMap = new HashMap<>();
        int maxCnt = 0;
        for (int[] req : requirements) {
            // Use length (end_i + 1) as key
            reqMap.put(req[0] + 1, req[1]);
            maxCnt = Math.max(maxCnt, req[1]);
        }

        // dp[j] will store the number of permutations of length `i` with `j` inversions.
        long[] dp = new long[maxCnt + 1];
        dp[0] = 1; // Base case: 1 permutation of length 0 ([]) with 0 inversions.

        for (int i = 1; i <= n; i++) {
            long[] newDp = new long[maxCnt + 1];
            long[] prefixSum = new long[maxCnt + 1];
            
            // Calculate prefix sums for the previous DP table (length i-1)
            prefixSum[0] = dp[0];
            for (int j = 1; j <= maxCnt; j++) {
                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;
            }

            // Calculate new DP table for length i
            for (int j = 0; j <= maxCnt; j++) {
                // Sum of dp[j-k] for k from 0 to i-1
                long ways = prefixSum[j];
                if (j >= i) {
                    ways = (ways - prefixSum[j - i] + MOD) % MOD;
                }
                newDp[j] = ways;
            }
            
            dp = newDp;

            // Apply requirement for the current length i
            if (reqMap.containsKey(i)) {
                int requiredCnt = reqMap.get(i);
                if (requiredCnt > maxCnt) { // Impossible requirement
                    return 0;
                }
                for (int j = 0; j <= maxCnt; j++) {
                    if (j != requiredCnt) {
                        dp[j] = 0;
                    }
                }
            }
        }

        // The problem guarantees a requirement for end = n-1 (length n).
        return (int) dp[reqMap.get(n)];
    }
}