Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
433
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define mp make_pair
  5. #define x first
  6. #define y second
  7.  
  8. using namespace std;
  9.  
  10. const int N = 100 * 1000 + 13;
  11. const int K = 100 + 7;
  12. const int MOD = 998244353;
  13.  
  14. int n, k, len;
  15. int a[N];
  16.  
  17. int pr[N][K];
  18. int pr2[N];
  19.  
  20. int add(int a, int b){
  21.     a += b;
  22.     if (a >= MOD) a -= MOD;
  23.     if (a < 0) a += MOD;
  24.     return a;
  25. }
  26.  
  27. pair<int, int> prv[N];
  28. int pos[N];
  29.  
  30. int get(int i, int j){
  31.     int res = max(0, i - len + 2);
  32.     if (prv[i].x != -1 && a[prv[i].x] != j)
  33.         res = max(res, prv[i].x + 1);
  34.     if (prv[i].y != -1 && a[prv[i].y] != j)
  35.         res = max(res, prv[i].y + 1);
  36.     return res;
  37. }
  38.  
  39. int main() {
  40.     scanf("%d%d%d", &n, &k, &len);
  41.     forn(i, n){
  42.         scanf("%d", &a[i]);
  43.         a[i] = max(-1, a[i] - 1);
  44.     }
  45.    
  46.     memset(pos, -1, sizeof(pos));
  47.     set<int> cur;
  48.    
  49.     forn(i, n){
  50.         if (a[i] != -1){
  51.             if (pos[a[i]] != -1)
  52.                 cur.erase(pos[a[i]]);
  53.             pos[a[i]] = i;
  54.             cur.insert(pos[a[i]]);
  55.         }
  56.            
  57.         if (cur.size() == 0)
  58.             prv[i] = mp(-1, -1);
  59.         else if (cur.size() == 1)
  60.             prv[i] = mp(*cur.rbegin(), -1);
  61.         else
  62.             prv[i] = mp(*cur.rbegin(), *(++cur.rbegin()));
  63.     }
  64.    
  65.     pr2[1] = 1;
  66.    
  67.     for (int i = 1; i <= n; ++i){
  68.         pr2[i + 1] = pr2[i];
  69.         forn(j, k)
  70.             pr[i + 1][j] = pr[i][j];
  71.         if (a[i - 1] == -1){
  72.             forn(j, k){
  73.                 int pos = get(i - 1, j);
  74.                 int val = add(add(pr2[i], -pr2[pos]), -add(pr[i][j], -pr[pos][j]));
  75.                 pr[i + 1][j] = add(pr[i + 1][j], val);
  76.                 pr2[i + 1] = add(pr2[i + 1], val);
  77.             }
  78.         }
  79.         else{
  80.             int j = a[i - 1];
  81.             int pos = get(i - 1, j);
  82.             int val = add(add(pr2[i], -pr2[pos]), -add(pr[i][j], -pr[pos][j]));
  83.             pr[i + 1][j] = add(pr[i + 1][j], val);
  84.             pr2[i + 1] = add(pr2[i + 1], val);
  85.         }
  86.     }
  87.    
  88.     printf("%d\n", add(pr2[n + 1], -pr2[n]));
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement