ARC187C

ARC187C

挺好的题，感谢大神 hyc 的指导。

鲜花：场上运气好通过了 D 没过 C，上了大分。

考虑直接模拟 P 序列的操作过程，假设当前操作了 1\sim i，那么当前的 P_i 一定是前缀最大值。

那么自然想到设状态 f_{i,j} 表示当前考虑了 1\sim i 的所有冒泡交换操作，P_i=j 且 \forall k < i \land Q_k >0，Q_k=P_k 的方案数。（此时 P_i 为前缀最大值）

现在考虑从 f_{i-1,k} 转移到 f_{i,j}，那么自然而然分为两种情况 Q_{i-1}=-1 和 Q_{i-1} \neq -1。

定义集合 S 为 Q_i 中所有出现过的正数集合，记 cnt_i 表示有多少个小于等于 i 的数没有出现在 S 内，w_i 表示前 i 个数中有多少个 Q_j=-1。

对于第一种情况，那么我们需要让 P_{i-1} 成为一个不在集合 S 里面的数，那么分两种情况，一种是第 i 个位置放比 k 大的数 j，那么要满足的 k 不在 S 内，这个可以前缀和优化做到 O(1)，第二种第 i 个位置放 比 k 小的数 v，那么会贡献到 f_{i,k} 且 v 不在 S 内，那么此时 v 的选法有 cnt_{k-1}-w_{i-1} 种，O(1) 转移。

第二种情况，需要让 P_{i-1}=Q_{i-1}，那么还是分为两种情况，一种是第 i 个位置填了 P_{i-1}，那么需要满足 k>P_{i-1}，贡献到 f_{i,k}，第二种是第 i 个位置填了 j，那么需要满足 j>a_{i-1}\land k=a_{i-1},都是 O(1) 转移的。

那么本题复杂度就是 O(n^2)，非常优美的一道题。

可以配合代码理解：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5003,H=998244353;
ll n,a[N],cnt[N],f[N],g[N],h[N];
bool ban[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)if(a[i]!=-1)ban[a[i]]=1;
    for(int i=1;i<=n;i++)cnt[i]=cnt[i-1]+(ban[i]==0),f[i]=1;
    for(int t=1,w=0;t<n;w+=a[t++]==-1)
    {
        memcpy(g,f,sizeof(g));memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)h[i]=(h[i-1]+(ban[i]==0)*g[i])%H;
        for(int i=1;i<=n;i++)
        {
            if(a[t]==-1)f[i]=(g[i]*(cnt[i-1]-w)+h[i-1])%H;
            else if(i>a[t])f[i]=(g[i]+g[a[t]])%H;
        }
    }
    cout<<f[n];
}