Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define mp make_pair
- #define x first
- #define y second
- using namespace std;
- const int N = 100 * 1000 + 13;
- const int K = 100 + 7;
- const int MOD = 998244353;
- int n, k, len;
- int a[N];
- int pr[N][K];
- int pr2[N];
- int add(int a, int b){
- a += b;
- if (a >= MOD) a -= MOD;
- if (a < 0) a += MOD;
- return a;
- }
- pair<int, int> prv[N];
- int pos[N];
- int get(int i, int j){
- int res = max(0, i - len + 2);
- if (prv[i].x != -1 && a[prv[i].x] != j)
- res = max(res, prv[i].x + 1);
- if (prv[i].y != -1 && a[prv[i].y] != j)
- res = max(res, prv[i].y + 1);
- return res;
- }
- int main() {
- scanf("%d%d%d", &n, &k, &len);
- forn(i, n){
- scanf("%d", &a[i]);
- a[i] = max(-1, a[i] - 1);
- }
- memset(pos, -1, sizeof(pos));
- set<int> cur;
- forn(i, n){
- if (a[i] != -1){
- if (pos[a[i]] != -1)
- cur.erase(pos[a[i]]);
- pos[a[i]] = i;
- cur.insert(pos[a[i]]);
- }
- if (cur.size() == 0)
- prv[i] = mp(-1, -1);
- else if (cur.size() == 1)
- prv[i] = mp(*cur.rbegin(), -1);
- else
- prv[i] = mp(*cur.rbegin(), *(++cur.rbegin()));
- }
- pr2[1] = 1;
- for (int i = 1; i <= n; ++i){
- pr2[i + 1] = pr2[i];
- forn(j, k)
- pr[i + 1][j] = pr[i][j];
- if (a[i - 1] == -1){
- forn(j, k){
- int pos = get(i - 1, j);
- int val = add(add(pr2[i], -pr2[pos]), -add(pr[i][j], -pr[pos][j]));
- pr[i + 1][j] = add(pr[i + 1][j], val);
- pr2[i + 1] = add(pr2[i + 1], val);
- }
- }
- else{
- int j = a[i - 1];
- int pos = get(i - 1, j);
- int val = add(add(pr2[i], -pr2[pos]), -add(pr[i][j], -pr[pos][j]));
- pr[i + 1][j] = add(pr[i + 1][j], val);
- pr2[i + 1] = add(pr2[i + 1], val);
- }
- }
- printf("%d\n", add(pr2[n + 1], -pr2[n]));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement