问题背景

在一场促销活动中，有 n 个人正在排队购买商品。每个人的身份分为两类：A类和B类，他们对排队位置有不同的偏好：

• A类人员希望自己的位置不早于指定的序号 |a_i|。
• B类人员则希望自己的位置不晚于指定的序号 |a_i|。

其中，若 a_i < 0 表示该人为A类，否则为B类。目标是计算满足所有约束条件的合法排队方式总数。

输入格式

第一行给出整数 n（表示人数），第二行为 n 个非零整数 a_1, a_2, ..., a_n，描述每个人的类型与要求。

样例分析

输入：
4
2 -2 -3 4

输出：
6

解释：共有4人，其中-2和-3为A类（必须在第2、第3位或更后），2和4为B类（必须在第2、第4位或更前）。满足条件的排列共6种。

解法思路

本题可通过动态规划结合组合数学求解。关键在于将不同类型的限制分别处理，并利用预处理阶乘优化排列数计算。

状态定义

设 dp[i][j] 表示处理完前 i 个位置时，已有 j 名A类人员被安排的方案数。

分类转移

1. A类人员（延迟出现）：对于要求不早于位置 k 的A类个体，在遍历到位置 i = k 时才开始允许其进入候选集合。使用累计计数器 s1 统计当前可选的A类人数。
2. B类人员（提前限制）：对于要求不晚于位置 k 的B类个体，必须确保其在位置 k 前完成分配。我们通过"延后校验"策略，在到达位置 i 时检查所有满足 |a_j| = i 的B类个体是否仍能安置。

组合数修正

当处理到第 i 个位置时，若有 c 个B类人员要求在此或之前完成入队，则需从剩余可用槽位中选出 c 个进行排列。设此时已放置 j 个A类人员，且此前已有 s2 个B类人员被安排，则剩余可用于这些B类人员的位置数为 i - j - s2。因此需要乘上排列数：

初始化与滚动数组优化

初始状态为 dp[0][0] = 1，即0个位置安排0人仅有一种方式。由于状态只依赖前一层，采用滚动数组减少空间开销。

算法实现

预处理阶乘及其逆元以支持快速排列数查询，时间复杂度为 O(n²)，符合题目规模限制。

代码框架

#include <bits/stdc++.h>
using namespace std;

const int N = 5005, MOD = 1e9 + 7;
int n, cntA[N], cntB[N], dp[2][N];
long long fac[N], invfac[N];

// 预处理阶乘与逆元
void initFac(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i-1] * i % MOD;
    invfac[n] = power(fac[n], MOD-2); // 快速幂求逆
    for (int i = n-1; i >= 0; --i)
        invfac[i] = invfac[i+1] * (i+1) % MOD;
}

long long perm(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] * invfac[n - r] % MOD;
}

int main() {
    cin >> n;
    initFac(n);
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] < 0) cntA[-a[i]]++;
        else cntB[a[i]]++;
    }

    dp[0][0] = 1;
    int cur = 0, totalA = 0, placedB = 0;

    for (int pos = 1; pos <= n; ++pos) {
        int nxt = cur ^ 1;
        memset(dp[nxt], 0, sizeof(dp[nxt]));
        totalA += cntA[pos];  // 新增可在pos及之后加入的A类人数

        for (int j = 0; j <= pos; ++j) {
            if (!dp[cur][j]) continue;

            // 放置一个A类人员
            if (j < totalA) {
                dp[nxt][j+1] = (dp[nxt][j+1] + 1LL * dp[cur][j] * (totalA - j)) % MOD;
            }

            // 不放A类，继续保留当前数量
            dp[nxt][j] = (dp[nxt][j] + dp[cur][j]) % MOD;
        }

        // 处理必须在pos前完成安排的B类人员
        if (cntB[pos] > 0) {
            for (int j = 0; j <= pos; ++j) {
                int available = pos - j - placedB;
                long long ways = perm(available, cntB[pos]);
                dp[nxt][j] = ways * dp[nxt][j] % MOD;
            }
        }

        placedB += cntB[pos];
        cur ^= 1;
    }

    cout << dp[cur][totalA] << endl;
    return 0;
}