AT_arc187_c [ARC187C] 1 Loop Bubble Sort 题解

首先考虑怎么刻画这个冒泡排序的过程，手玩一下可以发现，一轮冒泡排序把所有前缀最大值移到了下一个前缀最大值之前，且我们只做了这样的操作。

由于题目还要求了每个位置必须放什么数，因此我们平常用于求解排列个数的方法例如从小到大插入或是怎么计数一下都不太方便，因此不妨就从冒泡排序的过程入手设计思路。

在这里，前缀最大值是比较重要的，因此你可以考虑记录一下在我们目前构造出来的这个排列中，做一轮冒泡排序移到最前面的是什么数，设 f_{i,j} 表示我们已经填了 i 个数，同时进行的冒泡排序中目前移到最前面的是 j。

怎么转移呢？先考虑一下题目给的部分数被钦定了的限制，考虑我们怎么满足这个限制：这个数要么从前面被移过来，要么从后面被一次交换换过来，要么不动，而这些在我们转移到第 i 位的时候都是方便处理的。

还要注意一个问题：如果后面需要放的数被前面放了怎么办？这好办，直接前面钦定不要填就好了，设 sum_{i,j} 表示 [i+1,n] 这个区间中有多少个 q_k 使得 q_k\neq -1 且 q_k<j，可以得出转移：

• 若 a_i=-1，要么在下一个位置填一个比 j 大的数，注意这里如果 j 被后面钦定了，则不能进行此转移，因为你的 j 移不过去了，我们有 f_{i,j}\rightarrow f_{i+1,k}；要么在下一个位置填一个比 j 小的数，注意同样不能填填过的，有 (j-i-sum_{i,j})f_{i,j} \rightarrow f_{i+1,j}。

• 若 a_i \neq -1，那么如果 j=q_i，那么你下面必须填一个比 j 大的，但是这次不用考虑被后面选了，转移同上；否则你需要保证 j>q_i，且下一个位置就填 q_i，有 f_{i,j}\rightarrow f_{i+1,j}。

最后别忘了前面向比 j 大的转移需要前缀和优化，代码很短。

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        q[i]=read();
        if(q[i]!=-1)buc[q[i]]++;
    }
    if(q[n]!=-1 && q[n]!=n){write(0);return 0;}
    for(int i=1;i<=n;i++)f[1][i]=1;
    for(int i=1;i<n;i++){
        if(q[i]!=-1)buc[q[i]]--;
        for(int j=1;j<=n;j++)sum[j]=sum[j-1]+buc[j];
        for(int j=1;j<=n;j++){
            if(!f[i][j])continue;
            if(q[i]!=-1){
                if(q[i]==j) for(int k=j+1;k<=n;k++)Add(f[i+1][k],f[i][j]);
                else if(q[i]<j)Add(f[i+1][j],f[i][j]);
            }
            else{
                int tot=j-1-(i-1)-sum[j-1];
                if(tot<=0)continue;
                Add(f[i+1][j],mul(f[i][j],tot));
            }
        }
        if(q[i]==-1){
            int S=0;
            for(int j=1;j<=n;j++){
                Add(f[i+1][j],S);
                if(!buc[j])Add(S,f[i][j]);
            }
        }
    }
    write(f[n][n]);
    return 0;
}