分析：
先考慮如下問題。

求長度為n，逆序對為m的排列數量。

可以考慮dp，dp[i][j]定義為長度為i，逆序對為j的排列數量。

dp[1][0] = 1;
//枚舉排列長度，或者認為枚舉當前需要插到長度為i-1的排列中的數字
for(int i = 1; i <= n; ++i)  
{for(int j = 0; j <= i * (i + 1) / 2; ++j){//枚舉當前數字插到的位置，一共i個位置，分別可能使逆序對增加0~i-1個for(int k = 0; k < i; ++k){if(j >= k){dp[i][j] += dp[i - 1][j - k];}}}
}

在懂了上述dp之后，再來考慮本題。主要有兩個問題。

• 另外考慮，如果dp[i][j]是否依舊可以這樣求，因為上述問題中對于長度為i的排列，前i-1個數字確定的，i一定是最大的，我們只需要考慮它放在哪個位置即可。
• 如何同時滿足requirements[i][endi] = cnti和requirements[j][endj] = cntj,其中i!=j。

對于第一點，肯定是可以這樣求的，一方面我們不需要關心前i-1個數字是什么，只需要認為我們枚舉的第i個數字是這i個數字中最大的（類似上述思路）或者是最小的（與最大的等效并且更加方便理解上述dp的最內層循環）即可，另一方面我們看到至少有一個i滿足endi == n - 1。

對于第二點，我們只需要在dp的過程中適當修改。若$?en{d}_j==i$,則正常求$dp[i][cn{t}_j]$的值，而$dp[i][k]=0,k\ne cn{t}_j$。

AC代碼

class Solution {
public:int numberOfPermutations(int n, vector<vector<int>>& requirements) {const int mod = 1e9 + 7;vector<int> vt(305, -1);for(auto x: requirements) vt[x[0] + 1] = x[1];vector<vector<int>> dp(305, vector<int>(405, 0));dp[0][0] = 1;for (int i = 1; i <= n; ++i) {if (vt[i] != -1) {int j = vt[i];for (int k = 0; k < i; ++k) if (j >= k) dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;continue;}for (int j = 0; j <= min(400, (1 + i) * i / 2); ++j) {for (int k = 0; k < i; ++k) {if (j >= k) dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;}}}return dp[n][vt[n]];}
};
//dp數組定義為vector，如果定義為數組，一定記得先memset 0
//(dp[i][j] += dp[i - 1][j - k]) % mod不等價于dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
//(dp[i][j] += dp[i - 1][j - k]) % mod，模完之后值未賦給任何數。

上述代碼已經可以AC，但是可以進一步優化。

• dp[i][j]的遞推過程中，只用到了dp[i-1][j-k],故可以通過滾動數組優化空間。
• 對于最內層枚舉k的循環，我們發現遞推公式等價于$dp[i][j]={\sum }_{k=j?(i?1)}^{j}dp[i?1][k]$，即是dp[i-1]數組的一個前綴和，故可以預處理出前綴和，使得dp[i][j]實現O(1)遞推，優化為兩層循環。

優化后的代碼：

class Solution {
public:int numberOfPermutations(int n, vector<vector<int>>& requirements) {const int mod = 1e9 + 7;vector<int> vt(305, -1);for(auto x: requirements) vt[x[0] + 1] = x[1];vector<int> dp(405, 0);vector<int> sum(405, 0);dp[0] = 1;for (int i = 1; i <= n; ++i) {sum[0] = dp[0];for(int j = 1; j <= min(400, (1 + i) * i / 2); ++j) sum[j] = (sum[j - 1] + dp[j]) % mod;if (vt[i] != -1) {for(int j = 0; j <= min(400, (1 + i) * i / 2); ++j) dp[j] = 0;int j = vt[i];if(j < i) dp[j] = sum[j];else dp[j] = (sum[j] - sum[j - i] + mod) % mod;continue;}for (int j = 0; j <= min(400, (1 + i) * i / 2); ++j) {if(j < i) dp[j] = sum[j];else dp[j] = (sum[j] - sum[j - i] + mod) % mod;}}return dp[vt[n]];}
};