设 \(f_{i,j}\) 表示前 \(i\) 个位置,第 \(i\) 个位置的数字是 \(j\) 的方案数,\(s_i=\sum_{j}f_{i,j}\),\(mx_{i,j}\) 为位置 \(i\) 往前全是 \(j\) 的最长长度。
\(f_{i,j}=\left\{\begin{matrix} s_{i-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ mx_{i,j}\lt len \\ s_{i-1}-(s_{i-len}-f_{i-len,j}) \ \ \ \ \ mx_{i,j}\ge len \end{matrix}\right.\)
上面显然,因为随便选一定合法。
而 \(s_{i-1}-(s_{i-len}-f_{i-len,j})\) 的意义是,之前的随便选的方案数 \(s_{i-1}\),减去这个位置恰好出现了 \(len\) 个连续的方案数 \(s_{i-len}-f_{i-len,j}\),由于新加一个数只可能出现恰好 \(len\) 个的非法情况,所以这么减刚好就是真实的答案。
时间复杂度 \(\mathcal O(nk)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 105, mod = 998244353;
int n, k, len;
int a[N], f[N][M], s[N], mx[N][M];
int main() {
scanf("%d%d%d", &n, &k, &len);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
if (a[i] == j || a[i] == -1) mx[i][j] = mx[i - 1][j] + 1;
s[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j) {
if (a[i] == j || a[i] == -1) {
f[i][j] = s[i - 1];
if (mx[i][j] >= len) {
int tmp = (s[i - len] - f[i - len][j] + mod) % mod;
f[i][j] = (f[i][j] - tmp + mod) % mod;
}
s[i] = (s[i] + f[i][j]) % mod;
}
}
printf("%d", s[n]);
return 0;
}
标签:tmp,CF1093F,int,d%,len,mx,mod
From: https://www.cnblogs.com/Kobe303/p/16848051.html