[AGC065B] Erase and Insert

Genius_Star · 2026-09-04 10:45:05 · 题解

或许更好的阅读体验。

思路：

正着做太困难，考虑倒着做，即从 q 中从大到小开始，每次把 i 删掉然后再插入进去，问最后是 1 \sim n 的方案数。

那么显然，再操作 i 的时候，它插入的位置后面必须存在 i + 1 \sim n，因为它们依旧先操作了，相对位置是不会变的。

于是只有这个限制的话，可以 dp 了，定义 f_{i, j} 表示操作了 i \sim n 了，最后 i 插入的位置在 1 \sim i -1 这些数所在位置的排名为 j 的方案数。

转移时，考虑刷表，对于一个 f_{i + 1, j}，考虑 i 本身在 1 \sim i 位置的排名（显然后面的操作不会改变它们的相对顺序）设为 x：

• 如果 x < j，相当于 i + 1 插入的位置在 i 位置后面，所以 x 可以插入到 j 前面任何一个地方，即对于任意 k < j，有 f_{i, k} \gets f_{i, k} + f_{i + 1, j}。

• 否则 x \ge j，即 i + 1 插入在 i 前面，所以相当于需要将 x 插入到 j 前面（此时 j 前面会多一个数），所以它的排名可以是 j，所以这是对于任意 k \le j，有 f_{i, k} \gets f_{i, k} + f_{i + 1, j}。

你发现都是后缀加，是容易 O(1) 维护的，时间复杂度为 O(n^2)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 5e3 + 10, mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
int n;
int p[N], id[N], rk[N], f[N][N];
int main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        p[i] = read();
        id[p[i]] = i;
    }
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= i; ++j)
        rk[i] += (id[j] <= id[i]);
    f[n][n] = 1;
    for(int i = n; i >= 2; --i){
        int x = rk[i - 1];
        for(int j = i; j >= 1; --j)
          getadd(f[i][j], f[i][j + 1]);
        for(int j = 1; j <= i; ++j){
            // cerr << i << ' ' << j << ' ' << f[i][j] << '\n';
            if(x < j)
              getadd(f[i - 1][j - 1], f[i][j]);
            else
              getadd(f[i - 1][j], f[i][j]); 
        }
    }
    write(f[1][1]);
    return 0;
}