Підрахунок пар (Розбір)

Рішення

Ми можемо усунути середню частину і враховувати лише крайні ліві та праві частини.

Не існує жодного випадку, коли x+y \ge x^y , лише для пар $(2,2)$ та $(1,y)$, де $y$ - ціле число.

Ми виключаємо всі пари $(2,2)$, назвемо кількість двійок $f(2)$, потім виключаємо \frac{f(2) \times (f(2)-1)}{2}.

Ми виключаємо всі пари $(1,y)$ (включаючи одиниці), таким чином, ми виключаємо:

• пари $(1,1)$, тобто \frac{f(1) \times (f(1)-1)}{2}

• пари $(1,x)$, тобто f(1) \times (n-f(1)).

Потім наша відповідь готова!

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)