ARC169C Not So Consecutive

· · 题解

读错题了，写了一车组合数还在想为什么过不去最后一个样例。

更好的阅读体验 qwq

Description

给一个长度为 n 的序列 A，其中一些位置为 -1，其余位置的值域均在 [1,n] 之间。

你要给所有 -1 的位置填一个 [1,n] 之间的整数，要求满足：

求方案数，答案对 998\, 244\, 353 取模。n\le 5000。

Solution

设 f_{i,j} 表示填了前 i 个位置，第 i 个位置填的是 j 的方案数。那么枚举这个连续段的起点，朴素转移有

f_{i,j}=\sum_{k=\max(0,i-j)}^{i-1} [\forall l\in [k+1,i],A_l=-1 \text{ or } A_l=j]\sum_{col\neq j} f_{k,col}

这样直接做是 \mathcal{O}(n^4) 的，考虑优化。

首先方括号里那一串式子本质上是找 i 前面最后一个填了不为 j 的数的位置，设这个位置为 lst。

对每个数维护 pos_j 表示数 j 当前最后一次出现的位置。那么对于每个新的 i，我们记录 pos 的最大值和次大值即可。

这个过程对每个 i 可以 \mathcal{O}(n) 完成。式子变成了

f_{i,j}=\sum_{k=lst}^{i-1} \sum_{col\neq j} f_{k,col}

再把 col\neq j 这个条件容斥掉，有

f_{i,j}=\sum_{k=lst}^{i-1} \sum_{col=1}^n f_{k,col}-\sum_{k=lst}^{i-1}f_{k,j}

设 S_i=\sum\limits_{j=1}^i \sum\limits_{col=1}^n f_{i,col}，s_{i,j}=\sum\limits_{k=1}^i f_{k,j}，前缀和优化即可。时间复杂度 \mathcal{O}(n^2)。

#define int long long
const int N=5005,mod=998244353;
int pos[N],f[N][N],s[N][N],sum[N],n,a[N];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0][0]=1,sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=-1) pos[a[i]]=i;
        int mx1=0,mx2=0;
        for(int j=1;j<=n;j++) 
        {
            if(pos[j]>mx1) mx2=mx1,mx1=pos[j];
            else if(pos[j]>mx2) mx2=pos[j];
        }
        for(int j=1;j<=n;j++)
        {
            int lst=max(i-j,(a[mx1]==j)?mx2:mx1);
            f[i][j]=sum[i-1]-(lst?sum[lst-1]:0)-(s[i-1][j]-(lst?s[lst-1][j]:0));
            f[i][j]=(f[i][j]%mod+mod)%mod;
            s[i][j]=(s[i-1][j]+f[i][j])%mod;
            (sum[i]+=f[i][j])%=mod;
        }
        (sum[i]+=sum[i-1])%=mod;
    }
    cout<<(sum[n]-sum[n-1]+mod)%mod<<endl;
    return 0;
}