自动搬运

查看原文

来自洛谷，原作者为

	tuboshu666 **

搬运于2025-08-24 23:14:04，当前版本为作者最后更新于2025-04-23 16:23:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简化题意

共有 $N$ 次 INSERT 和 DELETE 操作，保证 INSERT 一定在 DELETE 前，且有 DELETE 必定有 INSERT，而 INSERT 可以单独存在。求合法方案的顺序数。

思路

将这 $N$ 次操作分成两类。一类有完整插入和删除操作，另一类仅有插入操作。

首先看插入和删除操作完整的一类。设有 $m$ 组完整操作配对。尝试将这 $m$ 组操作一组组插入。

插入第 $1$ 组，方案显然只有 $1$ 种。

插入第 $2$ 组，相当于在 $4$ 个位置中，选择 $2$ 个插入第二组的两个操作，方案数为 $\binom{4}{2}$。

插入第 $3$ 组，同理，相当于在 $6$ 个位置，认为另 $4$ 个顺序固定，选择 $2$ 个插入，方案数为 $\binom{6}{2}$。$\binom{6}{2}$ 是仅考虑第 $3$ 组有几种插入方式，再乘上另 $4$ 个位置的组合，即前 $2$ 组的组合数，即得插入到第 $3$ 组时的总方案数。

于是，这 $m$ 组操作的总方案数为：

再看仅有插入操作的一类。设该类操作有 $k$ 个。考虑在计算完第一类操作的情况下，插入这 $k$ 个操作。其中 $2m+k=N$。

与第一类相似，这 $k$ 个操作可以看做在 $n$ 个位置中，固定第一类 $2m$ 个操作的次序，选择 $k$ 个插入。由于这 $k$ 个操作不需要考虑任何顺序。因此，该类操作的方案数为：$\mathrm{A}_n^k$。

两类操作方案相乘即得最终答案。

Code

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
unordered_map<int,int> mp;
long long sum[N];
long long C[N][10]; //组合数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //组合数递推
    for (int i = 0 ; i <= 1e6 ; i++) C[i][0] = 1;
    for (int i = 1 ; i <= 1e6 ; i++)
    {
        for (int j = 1 ; j <= min(2,i) ; j++)
        {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] %= MOD;
        }
    }

    int n;
    cin >> n;
    int m = 0; //完整操作组数
    for (int i = 1 ; i <= n ; i++)
    {
        string type;
        cin >> type;
        if (type == "INSERT")
        {
            int x,y;
            cin >> x >> y;
            mp[x]++;
        }
        else
        {
            int x;
            cin >> x;
            mp[x]--;
            m++;
        }
    }

    long long ans = 1;
    int k = 2;

    //计算完整操作的组合数
    for (int i = 1 ; i <= m ; i++)
    {
        ans *= C[k][2];
        k += 2;
        ans %= MOD;
    }

    //计算insert的排列数
    for (int i = 2*m+1 ; i <= n ; i++)
    {
        ans *= i;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}