yicongli

CF1068D

Jan 21st, 2021
691
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int p=998244353;
  17. const int N=1e5+7;
  18.  
  19. int a[N];
  20. int f[N][205][2];
  21. int pre[205][2];
  22. int suf[205][2];
  23.  
  24. inline int add(const int &a,const int &b){
  25.     int t=a+b;
  26.     return t>=p?t-p:t;
  27. }
  28.  
  29. int main(){
  30.     // freopen(".in","r",stdin);
  31.     // freopen(".out","w",stdout);
  32.     int n;r(n);
  33.     for(int i=1;i<=n;++i){
  34.         r(a[i]);
  35.     }
  36.     if(~a[1]){
  37.         f[1][a[1]][0]=1;
  38.     }
  39.     else {
  40.         for(int i=1;i<=200;++i){
  41.             f[1][i][0]=1;
  42.         }
  43.     }
  44.     for(int i=1;i<=200;++i){
  45.         pre[i][0]=add(pre[i-1][0],f[1][i][0]);
  46.     }
  47.     for(int i=200;i;--i){
  48.         suf[i][0]=add(suf[i+1][0],f[1][i][0]);
  49.     }
  50.     for(int i=2;i<=n;++i){
  51.         for(int j=1;j<=200;++j){
  52.             if(~a[i] && j!=a[i])continue;
  53.             f[i][j][0]=add(f[i][j][0],add(pre[j-1][0],pre[j-1][1]));
  54.             f[i][j][1]=add(f[i][j][1],add(suf[j+1][1],add(f[i-1][j][0],f[i-1][j][1])));
  55.         }
  56.         for(int j=1;j<=200;++j){
  57.             pre[j][0]=add(pre[j-1][0],f[i][j][0]);
  58.             pre[j][1]=add(pre[j-1][1],f[i][j][1]);
  59.         }
  60.         for(int j=200;j;--j){
  61.             suf[j][0]=add(suf[j+1][0],f[i][j][0]);
  62.             suf[j][1]=add(suf[j+1][1],f[i][j][1]);
  63.         }
  64.     }
  65.     printf("%d\n",pre[200][1]);
  66.     return 0;
  67. }
RAW Paste Data