In this HackerEarth Count the permutations problem solution You are given two sequences A and B of length N. Determine the number of different ways to permute sequence A such that it is lexicographically smaller than the sequence B.

A sequence (X1,X2,...,Xk) is strictly lexicographically smaller than a sequence (Y1,Y2,...,YK), if there exists an index t (1 <= t <= K)  such that:
  1. Xt < Yt
  2. Xr = Yr for all 1 <= r < t
A permutation X of A is considered different from another permutation Y of A, if there exists an index i (1 <= i <= N) such that Xi != Yi. For example:

If A = (1,1,1), then there is only one different permutation of A. 
If A = (1,1,2,2), then there are 6 different permutations of A.


HackerEarth Count the permutations problem solution


HackerEarth Count the permutations problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
const int C = 2e5;
const int mod = 1e9 + 7;
int a[N];
int b[N];
int t[N];
void upd(int i,int v) {
for (;i <= C;i += i&(-i))
t[i] += v;
}
int que(int i) {
int ans = 0;
for (;i > 0;i -= i&(-i))
ans += t[i];
return ans;
}
int f[N];
int c[N];
int cnt[N];
int pow(int a,int b,int mod) {
int ans = 1;
while (b) {
if (b & 1)
ans = (1ll * ans * a) % mod;
a = (1ll * a * a) % mod;
b /= 2;
}
return ans;
}
int main(void) {
int n;
cin>>n;
for (int i = 1;i <= n;++i)
cin>>a[i],++cnt[a[i]];
for (int i = 1;i <= n;++i)
cin>>b[i];
f[0] = c[0] = 1;
for (int i = 1;i <= C + 55;++i) {
f[i] = (1ll * f[i - 1] * i) % mod;
c[i] = pow(f[i],mod - 2,mod);
}
int comb = f[n];
for (int i = 1;i <= C;++i)
comb = (1ll * comb * c[cnt[i]]) % mod;
for (int i = 1;i <= C;++i)
upd(i,cnt[i]);
int ans = 0;
for (int i = 1;i <= n;++i) {
comb = (1ll * comb * pow(n - i + 1,mod - 2,mod)) % mod;
ans = (ans + 1ll * comb * que(b[i] - 1)) % mod;
comb = (1ll * comb * cnt[b[i]]) % mod;
--cnt[b[i]];
if (cnt[b[i]] < 0)
break;
upd(b[i],-1);
}
cout << ans << '\n';
return 0;
}

Second solution

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
b=np.array(list(map(int,input().split())))
assert (n,)==a.shape and (n,)==b.shape and n<=100000 and n>=1 and np.sum(a>200000)==0 and np.sum(b>200000)==0 and np.sum(a<0)==0 and np.sum(b<0)==0, exit(1)
dict={}
kind=0
for el in a:
if el in dict:
dict[el]+=1
else:
dict[el]=1
kind+=1
bit=[0 for i in range(200002)]
def add(pos,x):
pos+=1
while pos<200002:
bit[pos]+=x
pos+=pos&-pos
def sum(pos):
pos+=1
r=0
while pos:
r+=bit[pos];
pos-=pos&-pos
return r
for el in a:
add(el,1)
MOD=1000000007
ans=0
fac=[1 for i in range(200002)]
for j in range(1,200002):
fac[j]=fac[j-1]*j
fac[j]%=MOD
inv=[pow(fac[i],MOD-2,MOD) for i in range(200002)]
D=1
for u in dict:
D*=inv[dict[u]]
D%=MOD
for i in range(n):
F=sum(b[i]-1)
#print(F)
F*=fac[n-i-1]*D
#print(fac[n-i-1])
F%=MOD
ans+=F
if b[i] in dict and dict[b[i]]!=0:
D*=fac[dict[b[i]]]
D*=inv[dict[b[i]]-1]
D%=MOD
dict[b[i]]-=1
add(b[i],-1)
else:
break
ans%=MOD
print(str(ans))