题解：AT_utpc2023_p Priority Queue 3

· · 题解

为了方便，这里把 A 数组降序排序。

设在某一时刻当前还没有被弹出的 A 集合内最大的元素为 A_j，则之后插入一个不属于 A 的数 x 时必须满足 x>A_j。证明考虑如果插入了一个数 x<A_j 且 x\not\in A 则以后想要把 A_j 弹出来之前必须先弹出来 x，此时 Y 中出现了不属于 A 集合中的元素。

如果某一时刻 - 操作之前堆中有 A 集合内的元素，并且所有插入的非 A 集合元素都大于当前最大的没有被弹出的 A_j 则 - 操作弹出的元素必然属于 A 集合。

考虑维护当前时刻的 A_j 值。考虑贡献延后处理，插入一个属于 A 集合中的元素时先只确定这个位置放的是 A 集合内元素，暂时不确定具体放的是哪一个数。只有当前最大没有被弹出的 A_j 被弹掉的时候再统一给之前的位置分配具体的 A 值。

具体的：设 f_{i,j,k,o} 表示当前已经处理完了串 S 的前 i 个操作，当前还没有进入 Y 集合的最大 A 元素是 A_j，当前 X 集合中有 k 个属于 A 集合的元素，A_j 自己目前是否已经在 X 集合中（o=1/0），有多少种不同的合法加入集合顺序。

初始条件显然就是 f_{0,0,0,0}=1。这里 X 集合中其他属于 A 集合的元素暂时先不考虑是谁。

然后考虑如果当前遇到了一个 + 操作，则先设前 i 次操作中有 p 个 + 操作和 q 个 - 操作，则当前 X 集合的大小就是 p-q。

考虑如果插入非 A 集合的元素，则只能选择 x>A_j\land x\not\in A 的元素 x 插入，这样的元素 x 的数量为 n-A_j-j。而此时用掉的非 A 集合元素数是 p-q-k，这些元素显然都在当前满足条件 x>A_j\land x\not\in A，因此这次操作可选的非 A 集合元素个数就是 n-A_j-j-p+q+k，转移就是 f_{i+1,j,k,o}\leftarrow f_{i+1,j,k,o}+f_{i,j,k,o}(n-A_j-j-p+q+k)。

如果当前插入 A 集合中的元素，则状态中的 k 值肯定会自增 1。如果当前插入的值恰好就是 A_j 则只有 o=0 的时候才是被允许，此时让 o\leftarrow 1 即可，转移就是 f_{i+1,j,k+1,1}\leftarrow f_{i+1,j,k+1,1}+f_{i,j,k,o}。

如果当前插入的值恰好不是 A_j，则先不管这个插入的元素是谁也暂时先不考虑贡献，直接转移即 f_{i+1,j,k+1,o}\leftarrow f_{i+1,j,k+1,o}+f_{i,j,k,o}。

然后考虑如果当前遇到了一个 - 操作，则此时因为弹出的元素必须属于 A 集合，所以这里必须先保证 k>0 才能继续转移。

同样考虑分类讨论：

如果当前弹出的元素不是 A_j，则：

总结一下，如果当前 k>0 且 k=1,o=1 两个条件不同时成立，这次操作就会弹出一个匿名的 A 集合内元素，转移就是 f_{i+1,j,k-1,o}\leftarrow f_{i+1,j,k-1,o}+f_{i,j,k,o}。这里继续不乘 k 是因为当前小根堆弹哪个元素实际上由具体的值唯一确定，而各个匿名元素的具体值继续延后考虑，暂时不处理。

如果当前弹出的值是 A_j 则由上面的分析可知此时必然满足 k=1\land o=1，此时堆中唯一一个属于 A 集合的元素就是 A_j 所以这次 - 操作一定必须把 A_j 弹出。弹出后 X 集合中就没有任何属于 A 集合内的元素了。

考虑之前一共有 q-j 个已经被弹出，但是具体值还没有被确定的 A 集合内匿名元素，则现在考虑枚举其中有多少个原始的值属于紧接的 A_{j+1},A_{j+2},A_{j+3},\ldots。假设选择 m 个匿名位置分别赋值为 A_{j+1},A_{j+2},\ldots,A_{j+m} 则说明这连续的 m 个元素在之前已经被弹出来，新的没有被弹出的最大元素就是 A_{j+m+1}。简单组合一下，从 q-j 个匿名位置中选择 m 个位置然后把 m 个不同的值排列进去的方案数就是 \binom{q-j}mm!=\frac{(q-j)!}{(q-j-m)!}。因此此时堆所有 m\in[0,\min(M-j-1,q-j)] 都有转移 f_{i+1,j+m+1,0,0}\leftarrow f_{i+1,j+m+1,0,0}+f_{i,j,k,o}\times\frac{(q-j)!}{(q-j-m)!}。

直接按照上述 dp 转移时间时间复杂度看起来都是 O((N+M)M^3) 级别的，但是可以注意到只有最后一种特殊的转移因为需要处理之前没有处理的贡献需要额外转移 m 的值，但是该转移只会出现在 k=1\land o=1的状态上，因此总时间复杂度其实是 O((N+M)M^2) 级别的，可以通过该题。

:::success[Code] 代码中部分变量名和上文不同。

namespace lowspeed_song {

int fac[N], inv[N], ifac[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

char s[610];
int f[2][310][310][2], a[310];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m, q = 0; cin >> n >> m;
    scanf("%s", s);
    for (int i = 0; i < m; ++i) cin >> a[i];
    sort(a, a + m, greater<>());
    f[1][0][0][0] = 1;
    for (int i = 0; i < n + m; ++i) {
        memset(f[i & 1], 0, sizeof f[i & 1]);
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= m; ++k)
                for (int o : {0, 1}) {
                    if (s[i] == '+') {
                        if (n - a[j] - j - i + q + q + k > 0) f[i & 1][j][k][o] = (f[i & 1][j][k][o] + (n - a[j] - j - i + q + q + k) * f[~i & 1][j][k][o]) % mod;
                        if (j < m && !o && m - q - k > 0) f[i & 1][j][k + 1][1] = (f[i & 1][j][k + 1][1] + f[~i & 1][j][k][o]) % mod;
                        if (m - q - k + o > 1) f[i & 1][j][k + 1][o] = (f[i & 1][j][k + 1][o] + f[~i & 1][j][k][o]) % mod;
                    } else if (k) {
                        if (k != 1 || o != 1) f[i & 1][j][k - 1][o] = (f[i & 1][j][k - 1][o] + f[~i & 1][j][k][o]) % mod;
                        else for (int p = 0; p <= min(q - j, m - j - 1); ++p) f[i & 1][j + p + 1][0][0] = (f[i & 1][j + p + 1][0][0] + f[~i & 1][j][k][o] * fac[q - j] % mod * ifac[q - j - p] % mod) % mod;
                    }
                }
        if (s[i] == '-') ++q;
    } cout << f[~(n + m) & 1][m][0][0] << '\n';
}

} // namespace lowspeed_song

:::