[Codeforces Educational Round 56] F Vasya and Array

题目大意

定义一个数列是好的,当且仅当它的任何长为 lenlen 的连续子序列包含至少两种数字。现给出一个长为 nn 的数列,每个位置是 1k1 \sim k 中的数或 1-1,要求替换所有的 1-11k1 \sim k 中的数,使得该数列为好数列,求替换的方案数。

1lenn100,0001 \leq len \leq n \leq 100,000

1k1001 \leq k \leq 100

题目链接

Codeforces Educational Round 56 - F

题解

考虑 DP,f(i,j)f(i, j) 表示已经考虑了前 ii 个数,最后一个是 jj 的答案,则在不考虑要求的情况下,有:

f(i,j)=j=1kf(i1,j)f(i, j) = \sum_{j' = 1}^{k} f(i - 1, j')

然后考虑减去不合法的情况,由于更早的不合法情况已经考虑过了,只需考虑 [ilen+1,i][i - len + 1, i] 这个区间(如果 ilen+1>0i - len + 1 > 0),它们只有都是 jj 的情况下才不合法,这需要原数列中该区间内只有 jj1-1,此时减去不合法的情况数,也就是前 ileni - len 个数的答案,此时如果第 ileni - len 个数也为 jj,那么它在计算 f(i1,j)f(i - 1, j) 时就被考虑了,故减去 j=1kf(ilen,j)f(ilen,j)\sum_{j' = 1}^{k} f(i - len, j') - f(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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>

const int MAXN = 100005;
const int MAXK = 105;
const int MOD = 998244353;

int f[MAXN][MAXK], a[MAXN], cnt[MAXK][MAXN];

int main() {
int n, k, len;
scanf("%d %d %d", &n, &k, &len);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++)
cnt[i][j] = cnt[i][j - 1] + (a[j] == -1 || a[j] == i);

f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) if (a[i] == -1 || a[i] == j) {
f[i][j] = f[i - 1][0];

if (i >= len && cnt[j][i] - cnt[j][i - len] == len) {
f[i][j] -= f[i - len][0];
f[i][j] < 0 ? f[i][j] += MOD : 0;
f[i][j] += f[i - len][j];
f[i][j] >= MOD ? f[i][j] -= MOD : 0;
}

f[i][0] += f[i][j];
f[i][0] >= MOD ? f[i][0] -= MOD : 0;
}
}

int ans = a[n] == -1 ? f[n][0] : f[n][a[n]];
printf("%d\n", ans);

return 0;
}