提出 #50047211

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

const int N=3000;
int a[N+10];
bool exist[N+10]; // v[i] = i出现过
int l[N+10]; // l[value] = 比l小的 未填的个数
int lp[N+10]; // lp[idx] = 比idx小的 未填位置的个数
mint fac[N+10]={1};
mint ifac[N+10];
mint inv[N+10];
mint binom(int n,int m){ return (m > n or m < 0)?0: fac[n]*ifac[m]*ifac[n-m]; }
mint sum(ll a,ll b) {
  if(a > b) return 0;
  assert(a<=b);
  return (a+b)*(b-a+1)/2;
}

int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N]=fac[N].inv();
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,1,N) inv[i] = ifac[i]*fac[i-1];
  int n=read();
  rep(i,1,n+1) a[i]=read();
  rep(i,1,n+1) if(a[i]!=-1) exist[a[i]]=1;
  ll x=0; // -1的个数
  rep(i,1,n+1) x+=a[i]==-1;
  // 计算比
  int cnt = 0;
  rep(v,1,n+1) {
    if(!exist[v]) cnt++;
    else l[v] = cnt;
  }
  cnt = 0;
  rep(i,1,n+1) {
    if(a[i] == -1) cnt++;
    else lp[i] = cnt;
  }
  mint ans = 0;
  // (l0,r0,l1,r1)
  // A 2个确定: A=逆序对个数
  mint A = 0;
  rep(i,1,n+1) if(a[i] != -1) rep(j,i+1,n+1) if(a[j] != -1 and a[j] < a[i]) A++;
  // B 1个确定:
  // C 0个确定:

  // (A,A)
  ans += A*A*fac[x];

  // (A,B),(B,A)
  rep(i,1,n+1) if(a[i] != -1) {
    // (p,i) A
    ans+=lp[i]*(x-l[a[i]])*fac[x-1]*A*2; // 左侧位置,更大值,剩余随便放, 对称x2
    // (i,p) A
    ans+=(x-lp[i])*l[a[i]]*fac[x-1]*A*2; // 右侧位置,更小值,剩余随便放, 对称x2
  }

  // (A,C),(C,A)
  ans += fac[x]*binom(x,2)*inv[2]*A*2; // 所有排列，选2个位置，1/2产出率，A的方案，对称

  // (C,C)
  //    (l0,r0) == (l1,r1)
  ans += fac[x]*binom(x,2)*inv[2]; // 所有排列，选2个位置，1/2产出率
  //    l0 == l1, or  r0 == r1
  ans += fac[x]*binom(x,3)*inv[3]*2*2;// 选3个位置(p0,p1,p0,p2)，1/3产出率,p1和p2交换,前组和后组交换
  //    l0 < r0 = l1 < r1, l1 < r1 = l0 < r0
  ans += fac[x]*binom(x,3)*inv[6]*2;// 选3个位置(p0,p1,p1,p2)，1/6产出率, 前组和后组交换
  //    4个坐标都不一样
  ans += fac[x]*binom(x,4)*6*ifac[4]*6;// 选4个位置(p0,p1,p2,p3)，6/4!产出率, 6种p的交换

  // (B,C),(C,B), 固定的下标i,未固定的下标p,q,l
  rep(i,1,n+1) if(a[i] != -1) {
    // 互不相同
    // (p,i) (q,l)
    ans+=lp[i]*(x-l[a[i]])*fac[x-1]*binom(x-1,2)*inv[2]*2;//左侧,更大值,剩余排列,选2个位置,1/2产出率,对称x2
    // (i,p) (q,l)
    ans+=(x-lp[i])*l[a[i]]*fac[x-1]*binom(x-1,2)*inv[2]*2;//右侧,更小值,剩余排列,选2个位置,1/2产出率,对称x2
    // 有共用下标
    // (p,i) (p,l)
    ans+=sum(x-lp[i],x-1)*sum(l[a[i]],x-1)*fac[x-2]*2;//p,l下标枚举,值枚举,剩余排列,对称x2
    // (i,p) (l,p)
    ans+=sum(lp[i],x-1)*sum(x-l[a[i]],x-1)*fac[x-2]*2;//p,l下标枚举,值枚举,剩余排列,对称x2
    // (p,i) (l,p)
    ans+=binom(lp[i],2)*binom(x-l[a[i]],2)*fac[x-2]*2;//更小下标x2,更大值x2,剩余排列,对称x2
    // (i,p) (p,l)
    ans+=binom(x-lp[i],2)*binom(l[a[i]],2)*fac[x-2]*2;//更大下标x2,更小值x2,剩余排列,对称x2
  }

  // (B,B)
  rep(i,1,n+1) if(a[i] != -1) {
    // (i,p),(i,p)
    ans+=binom(x-lp[i],1)*binom(l[a[i]],1)*fac[x-1];//更大下标x1,更小值x1,剩余排列
    // (p,i),(p,i)
    ans+=binom(lp[i],1)*binom(x-l[a[i]],1)*fac[x-1];//更小下标x1,更大值x1,剩余排列
    // (i,p),(i,q)
    ans+=binom(x-lp[i],2)*binom(l[a[i]],2)*fac[x-2]*4;//更大下标x2,更小值x2,剩余排列,下标和值交换x4
    // (p,i),(q,i)
    ans+=binom(lp[i],2)*binom(x-l[a[i]],2)*fac[x-2]*4;//更小下标x2,更大值x2,剩余排列,下标和值交换x4
    // (p,i,i,q), (i,p,q,i)
    ans+=lp[i]*(x-lp[i])*l[a[i]]*(x-l[a[i]])*fac[x-2]*2;//小下标,大下标,大值,小值,剩余排列,对称x2
  }
  rep(i,1,n+1) if(a[i] != -1) rep(j,i+1,n+1) if(a[j] != -1) { // i < j, O(n^2)
    // (i,p,j,p) 更大坐标，更小值，剩余排列，交换ij
    ans+=(x-lp[j])*l[min(a[i],a[j])]*fac[x-1]*2;
    // (p,i,p,j) 更小坐标，更大值，剩余排列，交换ij
    ans+=lp[i]*(x-l[max(a[i],a[j])])*fac[x-1]*2;
    // (i,p,p,j) 更小坐标，更大值，剩余排列，交换ij
    ans+=(lp[j]-lp[i])*max(0,l[a[i]]-l[a[j]])*fac[x-1]*2;

    // (i,p,j,q) 选>j,选>i,选小值,再选大值,剩余排列,交换
    ans+=(x-lp[j])*(x-lp[i]-1)*(l[min(a[i],a[j])])*(l[max(a[i],a[j])]-1)*fac[x-2]*2;
    // (p,i,q,j) 选<i,选<j,选大值,再选小值,剩余排列,交换
    ans+=(lp[i])*(lp[j]-1)*(x-l[max(a[i],a[j])])*(x-l[min(a[i],a[j])]-1)*fac[x-2]*2;
    // (p,i,j,q) <i,>j,
    if(a[i] > a[j]) { // a[p] > a[i] > a[j] > a[q]
      ans+=(lp[i])*(x-lp[j])*(x-l[a[i]])*(l[a[j]])*fac[x-2]*2;
    }else { // a[p] > a[i], a[i] < a[j], a[j] > a[q]
      // a[p] > a[j]
      ans+=(lp[i])*(x-lp[j])*(x-l[a[j]])*(l[a[j]])*fac[x-2]*2;
      // a[j] > a[p] > a[i]
      ans+=(lp[i])*(x-lp[j])*(l[a[j]]-l[a[i]])*(l[a[j]]-1)*fac[x-2]*2;
    }

    // (i<p,q<j), a[i] > a[p], a[q] > a[j]
    mint posmul = 0;
    posmul += (lp[j]-lp[i])*(lp[j]-1); //    i < p < j, q < j
    posmul += (x-lp[j])*(lp[j]);       //    i < j < p, q < j
    if(a[j] > a[i]){ // a[q] > a[j] > a[i] > a[p]
      ans+=posmul*(l[a[i]])*(x-l[a[j]])*fac[x-2]*2;
    }else{ // a[i] > a[j]
      // a[i] > a[p] > a[j]
      ans+=posmul*(l[a[i]]-l[a[j]])*(x-l[a[j]]-1)*fac[x-2]*2;
      // a[i] > a[j] > a[p]
      ans+=posmul*(l[a[j]])*(x-l[a[j]])*fac[x-2]*2;
    }
  }
  printf("%d\n",ans.val());
  return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘ll read()’:
Main.cpp:9:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果