交换

题目描述

给定一个 \({0, 1, 2, 3, … , n - 1}\) 的排列 p. 一个 \({0, 1, 2 , … , n - 2}\) 的排列 q 被认为是优美的排列, 当且仅当 q 满足下列条件:

对排列 \(s = {0, 1, 2, 3, ..., n - 1}\) 进行 \(n – 1\) 次交换.

  1. 交换 \(s[q_0], s[q_0 + 1]\)
  2. 交换 \(s[q_1], s[q_1 + 1]\)
  3. ......

最后能使得排列 \(s = p\).

问有多少个优美的排列, 答案对 \(10^9 + 7\) 取模.

输入格式

第一行一个正整数 \(n\).

第二行 \(n\) 个整数代表排列 \(p\).

输出格式

仅一行表示答案.

样例输入

3
1 2 0

样例输出

1

样例解释

\(q = {0,1}\)\({0,1,2}\)-> \({1,0,2}\)-> \({1, 2, 0}\)

\(q = {1,0}\)\({0,1,2}\)-> \({0,2,1}\)-> \({2, 0, 1}\)

数据范围

30%:\(n \leq 10\)

100%:\(n \leq 50\)

Explanation

以下是官方题解:

考虑倒着处理, 比如交换 \((i, i + 1)\), 那么前面的所有数不管怎么交换都无法到后面去 (下标恒小于等于 \(i\)) , 后面的数也是一样到不了前面. 说明这最后一次交换前, 就要求对于所有的 \(x \leq i, y \gt i，px \lt py\). 所以交换前左边的数是连续的, 右边也是 连续的. 由于交换前, 前面和后面的数是互相不干涉的, 所以就归结成了两个子问题. 于是 我们可以用记忆化搜索来解决这个问题.

设 \(dp[n][low]\) 代表长度为 \(n\),\(H\) 是 \({low, low + 1,...,low + n - 1}\) 的排列, 且 \(H\) 是 \(p\) 的子序列, 在 \(H\) 上优美序列的个数.

我们枚举交换哪两个相邻元素 \((k, k + 1)\), 然后判断 \(k\) 前面的所有数是否都小于后面的所有数, 如果是则进行转移 \(dp[n][low] += dp[k][low] \cdot dp[n – k][low + k] \cdot C_{n – 2}^{n – 1 - k}\). 即前面的 k 个元素与后面的 \(n - k\) 个元素是两个独立的子问题, 前面是 \({low ... low + k - 1}\) 的排列, 后面是 \({low + k ... low + n - 1}\) 的排 列,\(C_{n - 2}^{n - 1 - k}\) 代表的是在交换 \((k, k + 1)\) 前左右两边还分别要进 行\(n - 2\) 次交换, 而每次交换左边与交换右边是不同方案, 这相当于 \(n - 2\) 个位置选择 \(n - 1 - k\) 个位置填入, 故还需要乘上 $C_ {n-2} ^ {n-1-k}. 时间复杂度为 \(O(n^4)\).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 52;
const lli modr = 1000000007;

int n, arr[maxn];
lli dp[maxn][maxn];
lli C[maxn][maxn]; // The C in combinatorics

// This "judge" function should not be used~
bool judge(int pos_a_l, int pos_a_r, int pos_b_l, int pos_b_r)
{
    int max_a = 0, min_a = n,
        max_b = 0, min_b = n;
    // That is something we can optimize to O(1)
    for (int i = pos_a_l; i <= pos_a_r; i++)
        max_a = max(max_a, arr[i]),
        min_a = min(min_a, arr[i]);
    for (int i = pos_b_l; i <= pos_b_r; i++)
        max_b = max(max_b, arr[i]),
        min_b = min(min_b, arr[i]);
    // Now retrieved sufficient information, judging
    return max_a < min_b;
}

lli dfs(int len, int beg)
{
    // Already stored data in storage
    if (dp[len][beg] != -1)
        return dp[len][beg];
    // Single-status data, optimized instantly
    if (len == 1)
        return dp[len][beg] = 1;
    // Setting up reference for ease of coding
    lli &res = dp[len][beg];
    res = 0;
    int t[maxn], m = 0; // New array.
    // Copying and cloneing for new array
    for (int i = 1; i <= n; i++)
        if (arr[i] >= beg && arr[i] <= beg + len - 1)
            t[++m] = arr[i];
    // Swapping either two elements
    for (int k = 1; k <= m - 1; k++) {
        swap(t[k], t[k + 1]);
        int l = 0, r = 0;
        // Finding left & right boundaries
        for (l = 1; l <= k; l++)
            if (t[l] >= beg + k)
                break;
        for (r = k + 1; r <= m; r++)
            if (t[r] < beg + k)
                break;
        // Test
        if (l > k && r > m) {
            lli tmp = dfs(k, beg) * dfs(m - k, beg + k) % modr;
            tmp = tmp * C[m - 2][k - 1] % modr;
            res += tmp;
        }
        swap(t[k], t[k + 1]); // Unswapping
    }
    res %= modr;
    return res;
}

void generate_combinatory_numbers(void)
{
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % modr;
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        // arr[i]++; // For ease of demonstration
    }
    // That was a simple case of reading data.
    // Now we are going to dynamic programming procedure.
    generate_combinatory_numbers();
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = -1;
    dfs(n, 0);
    lli res = dp[n][0] % modr;
    printf("%lld\n", res);
    return 0;
}