Submission #947277

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int fact[1111111];
int inv[1111111];
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}

int C(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}

struct BIT{
    int N;
    vector<int>dat;
    void init(int n){
        N=n;
        dat.resize(N+1);
    }
    BIT(){}
    BIT(int n){init(n);}

    void add(int k,int x){
        for(k++;k<=N;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N;
int P[555555];

bool ex[555555];
int acc[555555];
signed main(){
    fact[0]=1;
    for(int i=1;i<1111111;i++)fact[i]=fact[i-1]*i%mod;
    inv[1111111-1]=mpow(fact[1111111-1],mod-2);
    for(int i=1111111-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;

    cin>>N;
    rep(i,N)cin>>P[i];
    rep(i,N)ex[P[i]]=true;
    for(int i=1;i<=N;i++){
        acc[i]=acc[i-1];
        if(!ex[i])acc[i]++;
    }


    int ans=0;
    int emp=0;

    int allemp=acc[N];
    BIT bit;bit.init(N+114);
    int sum=0;
    for(int i=N-1;i>=0;i--){
        int f=fact[N-i-1];
        if(P[i]){
            ans=(ans+bit.sum(P[i])*fact[allemp]%mod*f)%mod;
            int s=acc[P[i]];
            if(s){
                ans=(ans+fact[allemp-1]*emp%mod*s%mod*f)%mod;
            }
            bit.add(P[i],1);
            if(allemp)sum=(sum+fact[allemp-1]*(acc[N]-acc[P[i]]))%mod;
            continue;
        }
        int tmp=allemp*(allemp-1)/2;
        tmp%=mod;
        if(emp)ans=(ans+tmp*fact[allemp-2]%mod*emp%mod*f)%mod;
        ans=(ans+sum*f)%mod;
        emp++;
    }
    ans=(ans+fact[allemp])%mod;
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result