Codeforces 1093F.Vasya and Array

有点迷的容斥 + DP……

fi,jf_{i,j} 表示第 ii 个位置为 jj 的方案数,并有 si=j=1kfi,js_i = \sum\limits_{j = 1}^k f_{i,j}

首先只有 ai=ja_i = jai=1a_i = -1 的时候 fi,jf_{i,j} 有意义。
那么先不考虑限制条件,直接从 si1s_{i - 1} 继承所有方案。
然鹅有限制,显然当同时满足以下两点时有不合法状态:

  1. ileni \ge len
  2. 这一段可以通过修改 1-1jj 变成一样的。

这个时候,不合法的状态是 silenfilen,js_{i - len} - f_{i - len,j}
之所以要多算一个 filen,jf_{i - len,j},是因为各种容斥,会把它多减一次。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int K = 100;
const int mod = 998244353;
int n,k,len;
int a[N + 5],cnt[N + 5][K + 5],f[N + 5][K + 5],s[N + 5];
int main()
{
s[0] = 1;
scanf("%d%d%d",&n,&k,&len);
for(register int i = 1;i <= n;++i)
{
scanf("%d",a + i);
for(register int j = 1;j <= k;++j)
{
cnt[i][j] = cnt[i - 1][j] + (a[i] == j || a[i] == -1);
if(a[i] == j || a[i] == -1)
f[i][j] = ((s[i - 1] - (i >= len && cnt[i][j] - cnt[i - len][j] == len ? ((s[i - len] - f[i - len][j]) % mod + mod) % mod : 0)) % mod + mod) % mod;
s[i] = (s[i] + f[i][j]) % mod;
}
}
printf("%d\n",s[n]);
}

arknights