C++ 解题：最长上升子序列长度为 n-1 的排列计数

"用C++讲解以下题目：\nMX 在研究排列所具有的性质。这一天，她拿出了 \nn 张卡片排成一排，想要在上面填数以写成一个 \n1\n∼\nn 的排列。\n\nPiggy 趁 MX 不注意，偷偷在一些卡片上写了数。\n\n题目描述\nMX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 \nn\n−\n1\nn−1，MX 有多少种填数方法呢？\n\nPiggy 比较良心。他没有在不同的位置上填相同的数。\n\n输入格式\n本题有多组测试数据。\n\n第一行一个整数 \nT 代表数据组数。\n对于每组数据：\n\n第一行两个整数 \n, \nq 代表卡牌个数和 Piggy 已经填上了多少个数。\n第二行 \n2\nq 个整数，第 \n2\n−\n1\n, \n2\ni−1, \n2\ni 个整数 \n(\n, \n)\n(x,y) 代表第 \nx 个数被 Piggy 填成了 \ny。\n输出格式\n输出 \nT 行，每行一个整数代表答案。\n\n输入输出样例\n输入 #1复制\n2\n10 4\n2 2 4 8 6 5 7 6\n2 0\n输出 #1复制\n1\n1\n输入 #2复制\n2\n40 21\n1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40\n40 15\n3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39\n输出 #2复制\n4\n4\n说明/提示\n样例解释\n用 \n−\n1\n−1 代表此位置数字还未确定。\n样例 \n1\n：第一组给定的排列为 \n−\n1\n, \n2\n, \n−\n1\n, \n8\n, \n−\n1\n, \n5\n, \n6\n, \n−\n1\n, \n−\n1\n, \n−\n1\n−1,2,−1,8,−1,5,6,−1,−1,−1。容易发现，只有 \n1\n, \n2\n, \n3\n, \n8\n, \n4\n, \n5\n, \n6\n, \n7\n, \n9\n, \n10\n1,2,3,8,4,5,6,7,9,10 的最长上升子序列长度为 \n10\n−\n1\n=\n9\n10−1=9。第二组给定的排列为 \n−\n1\n, \n−\n1\n−1,−1，\n2\n, \n1\n2,1 为唯一满足要求的序列。\n\n本题采用捆绑测试。\n\nSubtask \n∑\nT\n∑n \n∑\nT\n∑q 分值\n0 \n≤\n10\n≤10 \n≤\n10\n≤10 10\n1 \n≤\n15\n≤15 \n≤\n10\n≤10 20\n2 \n≤\n5\n×\n1\n0\n3\n≤5×10 \n3\n \n≤\n5\n×\n1\n0\n3\n≤5×10 \n3\n 30\n3 \n≤\n5\n×\n1\n0\n5\n≤5×10 \n5\n \n≤\n5\n×\n1\n0\n5\n≤5×10 \n5\n 40\n保证 \n0\n≤\nq\n≤\nn0≤q≤n，\n1\n≤\nn\n≤\n5\n×\n1\n0\n5\n1≤n≤5×10 \n5\n ，\n1\n≤\nT\n≤\n1\n0\n5\n1≤T≤10 \n5\n ，\n1\n≤\nx\n, \ny\n≤\nn1≤x,y≤n。\n备注：规避超时\n备注：避免运行超时内容：这道题目可以使用动态规划来解决。\n\n首先，我们定义一个二维数组dp，其中dp[i][j]表示填完前i个数，且第i个数为j时的方案数。\n\n对于dp[i][j]的计算，有两种情况：\n\n1. 第i个数已经被Piggy填过。这种情况下，dp[i][j]的取值只能为dp[i-1][j]，表示第i个数不填任何数字。\n\n2. 第i个数没有被Piggy填过。这种情况下，dp[i][j]的取值可以为dp[i-1][j-1]，表示第i个数填为j；或者dp[i-1][j]，表示第i个数填为除了j以外的其他数字。\n\n因此，dp[i][j]的计算公式为：\ndp[i][j] = dp[i-1][j-1] + dp[i-1][j] (j <= q)\ndp[i][j] = dp[i-1][j] (j > q)\n\n最终的答案为dp[n][n-q]，表示填完所有的数且最长上升子序列长度为n-q的方案数。\n\n下面是C++的代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <cstring>\nusing namespace std; \n\nconst int MOD = 1e9 + 7; \nconst int MAXN = 5e5 + 5; \n\nint dp[MAXN][2 * MAXN]; \n\nint main() {\n int T; \n cin >> T; \n while (T--) {\n int n, q; \n cin >> n >> q; \n memset(dp, 0, sizeof(dp)); \n dp[0][0] = 1; \n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= 2 * q; j++) {\n if (j <= q) {\n dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD; \n } else {\n dp[i][j] = dp[i-1][j]; \n } \n } \n } \n cout << dp[n][n-q] << endl; \n } \n return 0; \n}\n\n\n时间复杂度分析：对于每组数据，需要计算dp数组的所有元素，因此时间复杂度为O(n * q)，其中n为卡牌个数，q为已经填上的数字个数。由于题目要求n最大为5 * 10^5，q最大为n，因此算法的时间复杂度在可接受范围内。\n