Submission #50087017

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353

long long dp[5005][5005]={0};
long long tot[5005]={0};
int a[5005];
int jud[5005][5005];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  for(int i=1;i<=n;i++){
    int f=-1;
    for(int j=i;j<=n;j++){
      if(a[j]!=-1){
        if(f==-1){f=a[j];}
        else if(f!=a[j]){f=-2;}
      }
      jud[i][j]=f;
    }
  }

  tot[0]=1;
  if(a[1]==-1){
    for(int i=1;i<=n;i++){dp[1][i]=1;}
    tot[1]=n;
  }
  else{
    dp[1][a[1]]=1;
    tot[1]=1;
  }

  for(int i=2;i<=n;i++){
    if(a[i]==-1){
      long long whole=0;
      for(int j=1;j<=n;j++){
        whole+=dp[i-1][j];
        whole%=mod;
      }
      for(int j=1;j<=n;j++){
        dp[i][j]=whole;
      }

      // treat prev == a[i]
      for(int j=1;j<=n;j++){
        int tg=i-j;
        if(tg>=1 && (jud[tg][i]==-1 || jud[tg][i]==j)){
          // cout << i << " " << j << "\n";
          dp[i][j]+=(mod-tot[tg-1]);
          dp[i][j]%=mod;
          dp[i][j]+=dp[tg-1][j];
          dp[i][j]%=mod;
        }
      }
    }
    else{
      for(int j=1;j<=n;j++){
        dp[i][a[i]]+=dp[i-1][j];
        dp[i][a[i]]%=mod;
      }

      // treat prev == a[i]
      int j=a[i];
      int tg=i-j;
      if(tg>=1 && (jud[tg][i]==-1 || jud[tg][i]==j)){
        dp[i][j]+=(mod-tot[tg-1]);
        dp[i][j]%=mod;
        dp[i][j]+=dp[tg-1][j];
        dp[i][j]%=mod;
      }
    }

    for(int j=1;j<=n;j++){
      tot[i]+=dp[i][j];
    }
    tot[i]%=mod;
  }

  // for(int i=1;i<=n;i++){
  //   for(int j=1;j<=n;j++){cout << dp[i][j] << " ";}
  //   cout << "\n";
  // }
  cout << tot[n] << "\n";
  return 0;
}

Submission Info

Judge Result