hello.

题解 CF1093F 【Vasya and Array】

2018-12-18 20:26:58


首发于 个人博客

思路

我们可以使用 $DP$ 解决这个问题。令 $f_{i,j}$ 为考虑前 $i$ 个数,第 $i$ 个数为 $j$ 的合法方案数,$s_i$ 等于 $\sum f_{i,j}$。

那么,$f_{i,j}$ 一定从 $s_{i-1}$ 转移而来,如果 $a_j$ 恰好等于 $j$ 或者 $-1$ 的话。但是,直接转移会包含不合法的情况。我们考虑,一些状态不合法,当且仅当:

  1. $i≥len$;
  2. 子区间 $\{a_1,\cdots,a_i\}$ 中所有的元素都等于 $−1$ 或者 $j$。

发现,满足以上两个条件的状态数实际上就是 $s_{i-len}-f_{i-len,j}$。转移的时候删去即可。

代码

#include <bits/stdc++.h>
#define md 998244353
#define maxn 100001
#define max(a,b) (a>b?a:b)
#define maxk 101
int n,k,len,a[maxn];
int f[maxn][maxk],s[maxn],cnt[maxn][maxk];
void inc(int &a,int b){a=((a+b>=md)?a+b-md:a+b);}
int main(){
    scanf("%d%d%d",&n,&k,&len);
    for (register int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=k;++j)
            inc(cnt[i][j],cnt[i-1][j]+(a[i]==j||a[i]==-1));
    for (register int i=1;i<=n;++i){
        for (register int j=1;j<=k;++j){
            if (!(a[i]==j||a[i]==-1)) continue;
            int add=1;
            if (i>1) add=s[i-1];
            inc(f[i][j],add);
            bool ok=i>=len;
            int l=max(1,i-len+1);
            ok&=(cnt[i][j]-cnt[l-1][j]==len);
            if (!ok) continue;
            if (i==len) {inc(f[i][j],md-1);continue;}
            int sum=f[i-len][j];
            inc(sum,md-s[i-len]);
            inc(f[i][j],sum);
        }
        for (register int j=1;j<=k;++j)
            inc(s[i],f[i][j]);
    }
    printf("%d\n",s[n]);
}