题解：AT_arc187_c [ARC187C] 1 Loop Bubble Sort

是青白呀 · 2024-11-18 22:13:52 · 题解

首先一个经典的结论是：一轮冒泡排序做的事，实际上是将序列按照每一个前缀最大值划分成若干个区间，并将每个区间的最大值（初始时在最前面）循环移位至区间末尾。

考虑记录前缀最大值进行 dp。我们预处理 pos_i 表示 Q 中值的位置，不存在则值为 0；num_i 表示 \leq i 的数中有多少个未在 Q 中出现；pren_i 表示 1\sim i 中 Q 上有多少个 -1。设 f_{i,j} 表示考虑到 P 的前 i 个数，当前前缀最大值为 j 的方案数。下面考虑转移：

• 若 P_i=j，也即当前位置是前缀最大值。此时 j 会向后移动，也即需要满足 pos_{j}\geq i 或 pos_j=0；同时上一个前缀最大值会被放在 i-1 的位置。设上一个前缀最大值为 k，我们需要满足 Q_{i-1}=k 或 pos_k=0。对于满足条件的 k<j，我们有 f_{i,j}\gets f_{i-1,k}。

• 若 P_i<j，则 P_i 会向前移动一位。继续根据 Q_i 的取值分类：

  • 若 Q_{i-1}\neq -1，则此时该位置只能填写 Q_{i-1}，且之前一定没有填写过这个数（由于其 pos 已经确定，故无论是否作为前缀最大值，转移都不合法）。故我们有 f_{i,j}\gets f_{i-1,j}。
  • 若 Q_{i-1}=-1，则该位置可以填未在 Q 中出现过、且之前的 -1 未被填过的小于 j 的数。此时，Q 中 i-1 之前的填在 -1 处的值一定小于 j，故剩余可行的值还有 num_{j-1}-pren_{i-2} 个。故我们有 f_{i,j}\gets f_{i-1,j}\times (num_{j-1}-pren_{i-2})。

使用前缀和优化掉第一种情况的枚举 k 的操作即可做到 O(n^2)。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define double long double
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5002,M=15,S=(1<<8)+5,inf=(ll)1e18+7,mo=998244353;
const double eps=1e-8;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int n,a[N];
int f[N][N],sum[N][N],pren[N],num[N],pos[N];
bool equ(int x,int v){
    if(a[x]>0)return a[x]==v;
    return !pos[v];
}
signed main(){
    read(n);
    rep(i,1,n){
        read(a[i]);
        if(a[i]!=-1)pos[a[i]]=i;
        pren[i]=pren[i-1]+(a[i]==-1);
    }
    if((a[n]>0&&a[n]!=n)||(a[n]==-1&&pos[n])){
        puts("0");
        return 0;
    }
    rep(i,1,n)
        num[i]=num[i-1]+(!pos[i]);
    f[0][0]=1;
    rep(i,0,n)
        sum[0][i]=1;
    rep(i,1,n){
        rep(j,1,n){
            //1.i is prefix max
            if(!pos[j]||pos[j]>=i)f[i][j]+=sum[i-1][j-1];
            //2.i isnot
            if(a[i-1]!=-1){
                if(a[i-1]<j)f[i][j]+=f[i-1][j];
            }
            else f[i][j]+=f[i-1][j]*(num[j-1]-(pren[i-1]-1));
            f[i][j]%=mo;
            sum[i][j]=(sum[i][j-1]+f[i][j]*equ(i,j))%mo;
        }
    }
    printf("%lld\n",f[n][n]);
    return 0;
}