Cards Permutation

                            Solution in C :

In   C++  :








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

typedef long long ll;

const ll mod = 1000*1000*1000+7;

vector<ll> fact;
int N, K;
vector<int> P;

struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4*N, 0);
}
void upd(int idx, int val, int l, 
int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = tree[2*n] + tree[2*n + 1];
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return L + R;
}
} bit, sub;

int main() {
fact.resize(500010);
fact[0] = 1;
for(int i = 1; i < 500010; i++) {
fact[i] = fact[i - 1] * i % mod;
}

scanf("%d", &N);
K = 0;
P.resize(N);
sub.init();
for(int i = 0; i < N; i++) {
scanf("%d", &P[i]);
P[i]--;
if(P[i] == -1) K++;
sub.upd(i, 1, 0, N - 1, 1);
}

ll sum = 1LL * N * (N - 1) / 2;
for(int i = 0; i < N; i++) {
if(P[i] != -1) sum -= P[i], sub.upd(P[i], 0, 0, N - 1, 1);
}
sum = (sum % mod + mod) % mod;

bit.init();
ll ans = 0;
ll tmp = 0;
int cnt = 0;
for(int i = 0; i < N; i++) {
if(P[i] == -1) {
ll a = sum * fact[K - 1] % mod;
ll b = tmp * fact[K - 1] % mod;
ll c = K < 2? 0 : (1LL * K * (K - 1) / 2 % mod) 
* fact[K - 2] % mod * cnt % mod;

ans += (a - b - c) * fact[N - i - 1] % mod,
 ans = (ans % mod + mod) % mod;


cnt++;
}
else {
bit.upd(P[i], 1, 0, N - 1, 1);
tmp += sub.quer(P[i] + 1, N - 1, 0, N - 1, 1);
tmp %= mod;

ll a = fact[K] * P[i] % mod;
ll b = fact[K] * bit.quer(0, P[i] - 1, 0, N - 1, 1) % mod;
ll c = K == 0? 0 : fact[K - 1] * sub.quer(
    0, P[i] - 1, 0, N - 1, 1) % mod * cnt % mod;

ans += (a - b - c) * fact[N - 1 - i] % mod, 
ans = (ans % mod + mod) % mod;
}
}
cout << (ans + fact[K]) % mod;
}









In   C :







#include<stdio.h>
int n, a[300100], pos[300100], 
mod = 1e9 + 7, occ[300100], 
les[300100], grt[300100], st[300100],
 lst[300100], gst[300100], bitree[300050];
void add(int idx, int val)
{
while( idx <= n )
{
bitree[idx] += val;
idx += ( idx & -idx );
}
}
int get(int idx)
{
int ans = 0;
while( idx > 0 )
{
ans += bitree[idx];
idx -= ( idx & -idx );
}
return ans;
}
long long fact[300100], factsumfr[300100], ans = 0;
long long pwr(long long a, long long b)
{
if( b == 0 )
{
return 1ll;
}
long long temp = pwr(a, b/2);
temp = ( temp * temp ) % mod;
if( b & 1 )
{
temp = ( temp * a ) % mod;
}
return temp;
}
long long inv(long long a)
{
return pwr(a, mod-2);
}
int main()
{
int i;
scanf("%d", &n);
for( i = 1 ; i <= n ; i++ )
{
scanf("%d", &a[i]);
pos[a[i]] = i;
if(a[i])
{
st[a[i]] = 1;
}
if(a[i])
{
occ[i] = 1;
}
}
fact[0] = 1;
for( i = 1 ; i <= n ; i++ )
{
les[i] = les[i-1] + occ[i], lst[i] = 
lst[i-1] + st[i], fact[i] = ( fact[i-1] * i ) % mod;
}
for( i = n ; i >= 1 ; i-- )
{
grt[i] = grt[i+1] + occ[i], gst[i] = gst[i+1] + st[i];
}
int k = les[n];
long long faci = fact[n-k],
 faci1 = fact[n-k-1], sumfrfr = 0;
for( i = 1 ; i <= n ; i++ )
{
if( a[i] == 0 )
{
sumfrfr = ( sumfrfr + ( ( fact[n-i] * (
     n - i - grt[i+1] ) ) % mod * inv(n-k-1) ) % mod ) % mod;
factsumfr[i] = ( 
    factsumfr[i-1] + fact[n-i] ) % mod;    
}
else
{
factsumfr[i] = factsumfr[i-1];
}
}
for( i = 1 ; i <= n ; i++ )
{
long long inc = 0;
if( st[i] == 0 )
{
inc += ( inc + ( ( sumfrfr * ( i - 1 - lst[i] )
 ) % mod * fact[n-k-1] ) % mod ) % mod;
}
else
{
inc = ( inc + ( ( ( n - i + 1 - gst[i] )
 * factsumfr[pos[i]] ) % mod * fact[n-k-1] )
  % mod ) % mod;
inc = ( inc + ( ( ( ( ( i - lst[i] )
 * fact[n-pos[i]] ) % mod * fact[n-k] ) % mod * (
      n - pos[i] + 1 - grt[pos[i]] ) ) % mod 
* inv(n-k) ) % mod ) % mod;
add(pos[i], 1);
int inv1 = get(n) - get(pos[i]);
inc = ( inc + ( ( fact[n-pos[i]] 
* fact[n-k] ) % mod * inv1 ) % mod ) % mod;
}
ans = ( ans + inc ) % mod;
}
ans = ( ans + fact[n-k] ) % mod;
printf("%lld\n", ans);
return 0;
}









In   Python3  :








import math
import os
import random
import re
import sys
from bisect import bisect , insort
N =  pow(10,9)+7
    
    
def update(bit, i, v):
    n = len(bit)
    while i < n :
        bit[i]+=v
        i+=i&(-i)

def getsum(bit, i):
    s=0
    while i>0 :
        s+=bit[i]
        i -= i&(-i)
    return s

def getnP(P,fixed):
    n = len(P)
    m = max(P)
    nI=[0]
    for i in range(2,n+1):
        nI.append(nI[-1] + fixed[i-2] ) 
    bit = [0 for i in range(m+1)]
    
    nP = [0 for i in range(n)]
    for i in range(n-1,-1,-1):
        if P[i] > 0 :
            nP[i] = nI[P[i]-1] - getsum(bit, P[i]-1) 
            update(bit, P[i], 1)  
        else :
            nP[i] = -1
    nP[0] = 0
    
    return nP
    
def solve(P):
    n = len(P)
    fixed = n*[0]
    
    for v in P:
        if v > 0 :
            fixed[v-1] = 1
            
    idZ   = [i for i in range(n) if P[i]==0 ]
    idNZ  = [i for i in range(n) if P[i]>0 ]
    vP    = [i for i in range(1,n+1) if not fixed[i-1]]
    nz    = len(idZ)
    nV,nZ,f = [0],[0],[1]

    for i in range(1,n):
        f.append( f[-1]*i %N )
        nV.append(nV[-1]+(not fixed[i-1])) 
        nZ.append(nZ[-1]+(not P[i-1]))
    f.append( f[-1]*n %N)          
    
    nP = getnP(P,fixed)

    Tnz = sum( ( P[i] - 1 - nP[i] ) * f[n-i-1] for i in idNZ  ) 
    Tz  = sum( ( i - nZ[i] ) * f[n-i-1] for i in idZ )
    S  = f[nz] * ( Tnz - Tz + 1) %N

    if nz > 0 :
        svP = sum(j-1 for j in vP)
        snPV = [0]
        for i in range(1,n):
            snPV.append( snPV[-1] + nV[P[i-1]-1]*(P[i-1]>0) )
        Tnz = sum( nZ[i] * nV[P[i]-1] * f[n-i-1] for i in idNZ )
        Tz  = sum( ( svP + snPV[i] ) * f[n-i-1] for i in idZ )
        S += f[nz-1] * ( Tz - Tnz ) %N
        
    if nz > 1 :
        Tz = sum( nZ[i] * f[n-i-1] for i in idZ ) * sum( nV[l-1] for l in vP if l>1 )
        S -= f[nz-2] * Tz %N
        
    return S%N
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    a = list(map(int, input().rstrip().split()))

    result = solve(a)

    fptr.write(str(result) + '\n')

    fptr.close()