思路与算法

把目标排列用相邻逆序交换还原到恒等，反转交换序列得到一个生成词。若长度不是n-1或任一相邻交换编号没有恰出现一次，答案0。否则相邻编号i,i+1的先后在等价词中不能改变，不相邻交换可交换顺序。记录各编号出现位置，转成路径上的大小关系。按编号从小到大构造它们执行时间的相对秩，DP[len][j]表示末项秩为j的方案，依相邻关系累加前一层合法秩。

正确性说明

泡排给出约化词；可行目标的每个生成元恰一次，所以不存在含重复生成元的三项辫关系，所有约化词仅靠不相邻生成元交换关联，故恰对应所列相邻顺序约束的线性扩展。秩DP添加最后编号时，旧秩小于j表示旧末项较早，旧秩至少j表示较晚，两类与约束一一对应，得到全部合法执行次序。

复杂度

泡排和验证O(N²)，秩DP采用直接两重秩累加，总O(N³)时间；每层清空O(N)，滚动数组O(N)，保存排列和词O(N²)上界（不可行时），N≤50。

易错点

n=1时空交换序列有一种。只看逆序对总数n-1还不够，必须每个交换编号都恰出现一次。模1e9+7。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
    int n;
    cin >> n;
    vector<int> p(n), word, cnt(max(0, n - 1));
    for (int &x : p)
        cin >> x;
    for (int i = 0; i < n; i++) {
        int at = find(p.begin() + i, p.end(), i) - p.begin();
        while (at > i) {
            swap(p[at], p[at - 1]);
            word.push_back(at - 1);
            cnt[at - 1]++;
            at--;
        }
    }
    if ((int)word.size() != n - 1 || any_of(cnt.begin(), cnt.end(), [](int x) {
            return x != 1;
        })) {
        cout << 0 << '\n';
        return 0;
    }
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    reverse(word.begin(), word.end());
    vector<int> pos(n - 1);
    for (int i = 0; i < n - 1; i++)
        pos[word[i]] = i;
    vector<long long> a(1, 1);
    for (int len = 2; len <= n - 1; len++) {
        vector<long long> b(len);
        for (int j = 0; j < len; j++)
            for (int k = 0; k < len - 1; k++)
                if ((pos[len - 2] < pos[len - 1] && k < j) ||
                    (pos[len - 2] > pos[len - 1] && k >= j))
                    b[j] = (b[j] + a[k]) % MOD;
        a.swap(b);
    }
    cout << accumulate(a.begin(), a.end(), 0LL) % MOD << '\n';
}