Counting Pairs (Editorial)

Solution

We can eliminate the mid term side , and only consider the leftmost and rightmost sides.

There is no case where x+y \ge x^y except for $(2,2)$ and $(1,y)$ where $y$ is integer.

We discount all pairs of $(2,2)$ , let the count of $2$ be $f(2)$ then we discount \frac{f(2) \times (f(2)-1)}{2}.

We discount all pairs of $(1,y)$ (including $1$'s) , so we remove :

• pairs of $(1,1)$ which is \frac{f(1) \times (f(1)-1)}{2}

• paris of $(1,x)$ which is f(1) \times (n-f(1)).

Then our Answer is ready !.

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    cnt=[0]*3
    for i in a:
        if(i<=2):cnt[i]+=1
    ans=(n*(n-1))//2
    ans-=(cnt[2]*(cnt[2]-1))//2
    ans-=(cnt[1]*(cnt[1]-1))//2
    ans-=(cnt[1])*(n-cnt[1])
    print(ans)