Cütlərin Sayılması (Həll təhlili)

Həll

Biz orta tərəfi aradan qaldıra bilərik və yalnız ən soldakı və ən sağdakı tərəfləri nəzərə alırıq.

x+y \ge x^y olan heç bir hal yoxdur, yalnız $(2,2)$ və $(1,y)$ halları üçün, burada $y$ tam ədəddir.

Biz $(2,2)$ cütlərinin hamısını çıxarırıq, $2$ sayını $f(2)$ olaraq adlandıraq, sonra \frac{f(2) \times (f(2)-1)}{2} çıxarırıq.

Biz $(1,y)$ (1-ləri də daxil olmaqla) cütlərinin hamısını çıxarırıq, belə ki, biz çıxarırıq:

• $(1,1)$ cütləri, yəni \frac{f(1) \times (f(1)-1)}{2}

• $(1,x)$ cütləri, yəni f(1) \times (n-f(1)).

Sonra cavabımız hazırdır!

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)