【算法精解】逆序对受限的方案数
题目：给定两个数 n ， k ，你需要求出 1 ， 2 ， . . . ， n 的所有排列 a 1 , a 2... ， a n 中满足 a 1 ＜ a 2 且逆序对个数 s u m ≤ k 的个数 , 答案对 1 0 9 ＋ 7 取模 题目：给定两个数n，k，你需要求出1，2，...，n的所有排列 a1,a2...，an中满足a1 ＜ a2且逆序对个数sum ≤ k的个数,答案对10^9＋7取模 题目：给定两个数n，k，你需要求出1，2，...，n的所有排列a1,a2...，an中满足a1＜a2且逆序对个数sum≤k的个数,答案对109＋7取模
输入描述
一行两个数 n , k , 3 ≤ n ≤ 200 , 0 ≤ k ≤ 200 一行两个数n,k, 3 ≤n≤ 200,0≤k≤200 一行两个数n,k,3≤n≤200,0≤k≤200
输出描述
输出一行一个数代表答案
解题思路
为了高效地解决这个问题，我们需要利用动态规划 (DP) 来计算满足条件的排列数。具体步骤如下：
1. 期望递减序列：
- 在一个排列中，逆序对是指对于任意的 i < j ，如果 a i > a j ，则 ( i , j ) i < j，如果 ai > aj，则 (i, j) i<j，如果ai>aj，则(i,j) 是一个逆序对。
- 我们需要计算的总逆序对数 s u m sum sum 是整个排列中的所有逆序对的数量。
2. 基本思路：
- 首先，考虑所有排列中满足 a1 < a2 的情况。
- 对于每一对可能的 (a1, a2) 组合，计算剩余的 n-2 个元素如何排列，使得整个排列的逆序对数 ≤ k。
- 将所有符合条件的 (a1, a2) 组合的排数相加，得到总解答。
3. 计算步骤：
Step 1: 枚举 a1 和 a2
- a1 可取值 1 到 n-1 的值。
- 对于每一对 a1，a2 可以取 a1 + 1 到 n 的值 (因为 a1 < a2)。
Step 2: 计算基础逆序对数
-
当 a1 和 a2 确定在排列的前两位时，逆序对数主要来自以下几个方面：
-
与 a1 和 a2 相关的逆序对：
- 如果 x < a1，则 x 会与 a1 和 a2 形成两个逆序对。
- 如果 a1 ≤ x < a2，则 x 只会与 a2 形成一个逆序对。
- 如果 x ≥ a2，则 x 不会与 a1 和 a2 形成逆序对。
-
通常来说，准备解析的部分对应的是剩余的逆序对。
-
Step 3: 动态规划计算剩余元素的逆序对数
-
定义 d p [ s ] [ t ] dp[s][t] dp[s][t] 表示 s 个元素的排列中包括 t 个逆序对的排列数。
-
递推公式：
d p [ s ] [ t ] = ∑ l = 0 m i n ( s − 1 , t ) d p [ s − 1 ] [ t − l ] dp[s][t] = \sum_{l=0}^{min(s-1,t)} dp[s-1][t-l] dp[s][t]=∑l=0min(s−1,t)dp[s−1][t−l]
其中，l 表示新加的 s 个元素可能会增加的逆序对的数量，插入位置的不同会导致逆序对数的变化。
-
初始条件：
d p [ 0 ] [ 0 ] = 1 dp[0][0] = 1 dp[0][0]=1
表示没有元素时，只有一种排列 (空排列)，逆序对数为 0。
Step 4: 确认理想解和
-
为了快速计算 d p [ s ] [ 0 ] dp[s][0] dp[s][0] 到 d p [ s ] [ t m ] dp[s][t_m] dp[s][tm] 的累加和，预先计算前缀和 p r e f i x s u m [ s ] [ t ] prefix_sum[s][t] prefixsum[s][t]：
p r e f i x s u m [ s ] [ t ] = ∑ x = 0 t d p [ s ] [ x ] prefix_sum[s][t] = \sum_{x=0}^{t} dp[s][x] prefixsum[s][t]=∑x=0tdp[s][x]
-
这样，在后续计算时，可以通过 p r e f i x s u m [ s ] [ t m a x ] prefix_sum[s][t_max] prefixsum[s][tmax] 快速得到 d p [ s ] [ 0 ] 到 d p [ s ] [ t m a x ] dp[s][0] 到 dp[s][t_max] dp[s][0]到dp[s][tmax] 的和。
Step 5: 求总答案
-
对于每一对 (a1, a2)，计算基础逆序对数 b a s e I n v e r s i o n = a 1 + a 2 − 3 baseInversion = a1 + a2 - 3 baseInversion=a1+a2−3。
-
解释： c 1 = a 1 − 1 c1 = a1 - 1 c1=a1−1 (小于 a1 的元素数量), c 2 = a 2 − a 1 − 1 c2 = a2 - a1 - 1 c2=a2−a1−1 (在 a1 和 a2 之间的元素数量)，则 base_inversion = 2 ∗ c 1 + c 2 = 2 ∗ ( a 1 − 1 ) + ( a 2 − a 1 − 1 ) = a 1 + a 2 − 3 2*c1 + c2 = 2*(a1 - 1) + (a2 - a1 - 1) = a1 + a2 - 3 2∗c1+c2=2∗(a1−1)+(a2−a1−1)=a1+a2−3。
-
计算剩余允许的逆序对数 t m a x = k − b a s e I n v e r s i o n t_max = k - baseInversion tmax=k−baseInversion。
- 如果 t_max < 0，则这 (a1, a2) 组合不可能满足条件，跳过。
- 否则，累加 prefix_sum[n-2][t_max] 到答案中。
-
最终，所有符合条件的 (a1, a2) 组合的排数相加即是答案。
package com.sky;import java.util.Scanner;public class Test1 {static final int MOD = 1_000_000_007;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), k = sc.nextInt();long[][] dp = new long[n - 1][k + 1];dp[0][0] = 1;for (int s = 1; s <= n - 2; ++s) {for (int t = 0; t <= k; ++t) {dp[s][t] = 0;for (int l = 0; l <= Math.min(s - 1, t); ++l) {dp[s][t] = (dp[s][t] + dp[s - 1][t - l]) % MOD;}}}long[][] prefix = new long[n - 1][k + 1];for (int s = 0; s <= n - 2; ++s) {prefix[s][0] = dp[s][0];for (int t = 1; t <= k; ++t) {prefix[s][t] = (prefix[s][t - 1] + dp[s][t]) % MOD;}}long ans = 0;for (int a1 = 1; a1 <= n - 1; ++a1) {for (int a2 = a1 + 1; a2 <= n; ++a2) {long baseInv = a1 + a2 - 3;if (baseInv > k) continue;int invMax = k - (int) baseInv;if (n - 2 == 0) {if (invMax >= 0) {ans = (ans + 1) % MOD;}continue;}if (invMax > k) invMax = k;ans = (ans + prefix[n - 2][invMax]) % MOD;}}System.out.println(ans);}
}