提出 #74382649

---

ソースコード 拡げる

#include<bits/stdc++.h>

// #define XAERIC666
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#ifndef XAERIC666
  #define xaeric(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
#else
  #define xaeric(...) 114514
#endif
int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
  while('0'<=c&&c<='9'){x=x*10+c-48;c=getchar();}
  return x*f;
}
// void in(int*a,int n){for(int i=1;i<=n;i++)a[i]=read();}
// void out(int*a,int n){for(int i=1;i<=n;i++)printf("%lld%c",a[i]," \n"[i==n]);}
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(b);i>=(a);--i)
#define YES puts("YES");
#define NO puts("NO");
using namespace std;

const int P=998244353;
const int N=5005;
int fac[N],ifac[N];
int qpow(int a,int k,int p=P){
  int r=1;
  while(k){
    if(k&1){
      r=r*a%p;
    }
    a=a*a%p;
    k/=2;
  }
  return r;
}
void zuhe(int n){
  fac[0]=1;
  for(int i=1;i<=n;i++){
    fac[i]=fac[i-1]*i%P;
  }
  ifac[n]=qpow(fac[n],P-2);
  for(int i=n-1;~i;i--){
    ifac[i]=ifac[i+1]*(i+1)%P;
  }
}
int c(int n,int m){
  if(n<0||m<0){
    return 0;
  }
  if(m>n){
    return 0;
  }
  return fac[n]*ifac[m]%P*ifac[n-m]%P;
}
int n,m,a[N],pre[N],suf[N];
int ans[N][N];
int cnt[N],v[N],x[N][N],y[N][N];
int pp[N];
void solve(){
  zuhe(N-5);
  n=read(),m=read();
  for(int i=1;i<=n;i++){
    a[i]=read();
    cnt[i]=cnt[i-1]+(a[i]==-1);
    v[a[i]]=1;
  }
  pre[0]=n;
  for(int i=1;i<=n;i++){
    pre[i]=pre[i-1];
    if(a[i]!=-1){
      pre[i]=min(pre[i],a[i]);
    }
    pp[i]=pp[i-1];
    if(!v[i]){
      pp[i]++;
    }
  }
  suf[n+1]=n;
  for(int i=n;i>=1;i--){
    suf[i]=suf[i+1];
    if(a[i]!=-1){
      suf[i]=min(suf[i],a[i]);
    }
    // xaeric("  + %lld\n",suf[i]);
  }
  for(int cc=0;cc<=cnt[n];cc++){
    x[cc][0]=0;
    for(int i=1;i<=n;i++){
      x[cc][i]=x[cc][i-1];
      if(!v[i]){
        x[cc][i]+=(c(pp[n-1]-pp[i-1],cc)-c(pp[n-1]-pp[i],cc)+P)%P*i%P;
        x[cc][i]%=P;
      }
    }
    for(int i=n;i>=1;i--){
      y[cc][i]=y[cc][i+1];
      if(!v[i]){
        y[cc][i]+=(c(pp[n-1]-pp[i-1],cc)-c(pp[n-1]-pp[i],cc)+P)%P;
        y[cc][i]%=P;
      }
    }
    // xaeric("! %lld\n",cc);
    // for(int i=1;i<=n;i++){
    //   xaeric("   + %lld %lld %lld\n",i,x[cc][i],y[cc][i]);
    // }
    ans[cc][0]=0;
    for(int m=1;m<=n;m++){
      ans[cc][m]=(x[cc][m-1]+y[cc][m]*m%P)%P*fac[cc]%P*fac[cnt[n]-cc]%P;
    }
  }
  for(int i=1;i<=m;i++){
    int x=read(),y=read();
    int tmp=min(pre[x-1],suf[y+1]);
    // xaeric("  ! %lld %lld\n",pre[x-1],suf[y+1]);
    printf("%lld\n",ans[cnt[n]-(cnt[y]-cnt[x-1])][tmp]);
  }
}

signed main(){
  int TTTT=1;
  // int TTTT=read();
  while(TTTT--){
    solve();
  }
}

提出情報

ジャッジ結果