HackerEarth Count the permutations problem solution

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.

`#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 npn=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=0for el in a:    if el in dict:        dict[el]+=1    else:        dict[el]=1        kind+=1bit=[0 for i in range(200002)]def add(pos,x):    pos+=1    while pos<200002:        bit[pos]+=x        pos+=pos&-posdef sum(pos):    pos+=1    r=0    while pos:        r+=bit[pos];        pos-=pos&-pos    return rfor el in a:    add(el,1)MOD=1000000007ans=0fac=[1  for i in range(200002)]for j in range(1,200002):    fac[j]=fac[j-1]*j    fac[j]%=MODinv=[pow(fac[i],MOD-2,MOD) for i in range(200002)]D=1for u in dict:   D*=inv[dict[u]]   D%=MODfor 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:        breakans%=MODprint(str(ans))`