Problem surface

analysis

Obviously, each permutation can be mapped to a unique integer through \ (\ text{Cantor Expansion} \), which is a bijection and meets the requirements of the topic.

\(\ text{Cantor Expansion} \) formula:

Now consider adding \ (0 \).

Obviously, the initial value is the sequence value (i.e. the contribution without \ (0 \) multiplied by \ (m! \). Now we need to consider the increment. (note that the serial number starts with \ (1 \)

There are \ (0 \) in \ (m \) positions, that is, the numbers in \ (m \) positions are erased. We find that giving some values to these \ (0 \) will affect the \ (A_i \) in front of it (excluding \ (0 \)), the \ (A_i \) of \ (0 \) in front of it (assuming there are already some values), and the \ (A_i \) in its own position.

If you calculate directly in this way, you need \ (O(nm! \log n) \) to consider optimization.

You might as well split each \ (0 \). First preprocess the set of \ (m \) numbers that can be filled by \ (0 \), sort them from small to large, and record them as \ (C \). Then preprocess the position of the \ (I \) th \ (0 \) and record it as \ (b_i \). Note that the number filled in the current \ (j \) \ (0 \) is \ (c_k \). When we consider the contribution of the \ (j \) th \ (0 \) to the \ (A_i \) of his previous \ (0 \), we only need to enumerate those cases where the \ (1\sim j-1 \) bit is greater than \ (c_k \). So I have contributed:

Now consider calculating the \ (A_i \) in front of it, which can be calculated directly by finding the reverse order pair. For the previous \ (A_i \), the increment is \ ((n-i)!\times (m-1)!\)， Well understood.

As for its own \ (A_i \), scanning this thing backwards is to find the reverse order pair. For the \ (j \) \ (0 \), the contribution formula is:

These things can be calculated with the time complexity of \ (O(nm^2 \log n) \). Extract irrelevant items and preprocess some prefixes and to achieve \ (O(nm \log n) \). Continue to observe that by directly counting the part of each bit \ (0 \) enumeration value (i.e. no more enumeration values), you can achieve \ (O(n \log n) \). The most beautiful way of writing can be to stop using \ (\ text{BIT} \) except the initial \ (\ text{Cantor Expansion} \).

code

#include<cstdio>
#include<algorithm>
#define int ll
typedef long long ll;
const int mod=1e9+7;
int n,s[300005],pref[300005],fac[300005],a[300005],vis[300005],b[300005],c[300005];
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline int min(const int &x,const int &y) {return x<y? x:y;}
inline void add(int x,int d) {for(;x<=n;x+=x&(-x)) s[x]=(s[x]+d)%mod;}
inline int ask(int x) {int res=0; for(;x;x-=x&(-x)) res=(res+s[x])%mod; return res;}
signed main() {
    n=read();int ans=0,num=0,tot=0,val=0;
    fac[0]=1;
    for(register int i=1;i<=n;++i) a[i]=read(),fac[i]=fac[i-1]*i%mod;
    for(register int i=1;i<=n;++i) {
        if(a[i]==0) b[++num]=i;
        vis[a[i]]=1;
    } val=num*(num-1)/2%mod;
    for(register int i=1;i<=n;++i) if(!vis[i]) c[++tot]=i;
    for(register int i=1;i<=num;++i) pref[i]=(pref[i-1]+fac[n-b[i]])%mod;
    // for(register int i=1;i<=num;++i) tmp1[i]=(tmp1[i-1]+num-i)%mod;
    // for(register int i=1;i<=num;++i) pref[i]=(pref[i-1]+fac[num-2]*fac[n-b[i]]%mod)%mod;
    for(register int i=n;i>=1;--i) {
        if(a[i]) {
            ans=(ans+fac[n-i]*ask(a[i]))%mod;//less minus
            // bas=(bas+fac[n-i]*ask(a[i]-1))%mod;
            add(a[i],1);
        }
    }
    ans=(ans+1)*fac[num]%mod;
    // printf("%d\n",ans);
    // for(register int i=1;i<=n;++i) s[i]=0;
    int sum1=0,sum2=0;
    for(register int i=1;i<=n;++i) {
        if(!a[i]) {
            int pos=std::lower_bound(b+1,b+1+num,(ll)i)-b,sum=0;
            // for(register int j=1;j<=num;++j) {
                // sum=(sum+(ask(n)-ask(c[j]))*fac[num-1]%mod)%mod;// Consider maintaining $\ sum directly_ {i=1}^{num} ask(c_i)$
                // sum=(sum+fac[num-2]*(num-j)%mod*pref[pos-1]%mod)%mod;// Extract irrelevant items
                // tmp=(tmp+min(pos-1,num-j))%mod;
                // for(register int k=1;k<pos;++k) sum=(sum+fac[num-2]*fac[n-b[k]]%mod*(num-j)%mod)%mod;
            // }
            // sum=(sum+(ask(n)*num%mod-ask(c[num]))%mod*fac[num-1]%mod)%mod;
            sum=(sum+(sum2*num-sum1)%mod*fac[num-1])%mod;
            sum=(sum+fac[num-2]*pref[pos-1]%mod*val)%mod;
            // tmp=tmp*pref[pos-1]%mod;
            ans=(ans+sum)%mod;
        }
        else {
            int pos=std::upper_bound(c+1,c+1+num,(ll)a[i])-c;
            // add(a[i],fac[n-i]*(num-pos+1));
            // add(a[i],fac[n-i]);
            if(a[i]<c[num]) sum1=(sum1+fac[n-i]*(num-pos+1))%mod;
            sum2=(sum2+fac[n-i])%mod;
        }
    }
    // for(register int i=1;i<=n;++i) s[i]=0;
    sum1=0;
    for(register int i=n;i>=1;--i) {
        if(!a[i]) {
            // int sum=0;
            // for(register int j=1;j<=num;++j) sum=(sum+fac[n-i]*ask(c[j]-1)%mod*fac[num-1]%mod)%mod;
            ans=(ans+sum1*fac[n-i]%mod*fac[num-1])%mod;
        }
        else {
            // add(a[i],1);
            int pos=std::upper_bound(c+1,c+1+num,(ll)a[i])-c;
            if(a[i]<c[num]) sum1=(sum1+(num-pos+1))%mod;
        }
    }
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}