【算法精解】逆序对受限的方案数

$题目：给定两个数n，k，你需要求出1，2，...，n的所有排列a1,a\mathrm{2...}，an中满足a1＜a2且逆序对个数sum\le k的个数,答案对10^9＋7取模$
输入描述
$一行两个数n,k,3\le n\le 200,0\le k\le 200$
输出描述
输出一行一个数代表答案

解题思路

为了高效地解决这个问题，我们需要利用动态规划 (DP) 来计算满足条件的排列数。具体步骤如下：

1. 期望递减序列：

• 在一个排列中，逆序对是指对于任意的 $i<j，如果ai>aj，则(i,j)$ 是一个逆序对。
• 我们需要计算的总逆序对数 $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: 动态规划计算剩余元素的逆序对数

• 定义 $dp[s][t]$ 表示 s 个元素的排列中包括 t 个逆序对的排列数。

• 递推公式：

  $dp[s][t]={\sum }_{l=0}^{min(s-1,t)}dp[s-1][t-l]$

  其中，l 表示新加的 s 个元素可能会增加的逆序对的数量，插入位置的不同会导致逆序对数的变化。

• 初始条件：

  $dp[0][0]=1$

  表示没有元素时，只有一种排列 (空排列)，逆序对数为 0。

Step 4: 确认理想解和

• 为了快速计算 $dp[s][0]$ 到 $dp[s][t_m]$ 的累加和，预先计算前缀和 $prefi{x}_{s}um[s][t]$：

  $prefi{x}_{s}um[s][t]={\sum }_{x=0}^{t}dp[s][x]$

• 这样，在后续计算时，可以通过 $prefi{x}_{s}um[s][t_{m}ax]$ 快速得到 $dp[s][0]到dp[s][t_{m}ax]$ 的和。

Step 5: 求总答案

• 对于每一对 (a1, a2)，计算基础逆序对数 $baseInversion=a1+a2-3$。

• 解释：$c1=a1-1$ (小于 a1 的元素数量), $c2=a2-a1-1$ (在 a1 和 a2 之间的元素数量)，则 base_inversion = $2\ast c1+c2=2\ast (a1-1)+(a2-a1-1)=a1+a2-3$。

• 计算剩余允许的逆序对数 $t_{m}ax=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);
    }
}