Problem:


Score : 400 points

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.

For each k=1, 2, ..., N, solve the following problem and print the answer.  

Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

3 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

For each k=1,2,...,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.

From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Wrong Answer

Solution code:
import copy
from scipy.misc import comb
 
n = map(int, input())
a = list(map(int, input().split()))
matches = {}
 
for i in range(len(a)):
  aa = copy.copy(a)
  del aa[i]
  for av in aa:
    if av in matches:
      matches[av] += 1
    else:
      matches[av] = 1
  combi_cnt = 0
  for v in matches:
    combi_cnt += comb(v, 2, exact=True)
  print(combi_cnt)

Submission status: Wrong Answer

Solution code:
import collections

N = 8#int(input())
#A = list(map(int, input().split()))
A = [1, 2, 1, 4, 2, 1, 4, 1]

c = collections.Counter(A)
#print(c)

count_dic = {}
for i in c.keys():
    count = 0
    c_copy = c.copy()
    c_copy[i] = c[i]-1
    #print(c_copy)
    for k in c.keys():
        count += int(c_copy[k]*(c_copy[k]-1)/2)
        count_dic[i] = count
        #print(count)
    #print(count_dic)

for i in range(N):
    print(count_dic[A[i]])

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

nn = int(input())
aa = list(map(int, input().split(' ')))

counts = {}
for a in aa:
    if a not in counts:
        counts[a] = aa.count(a)

exit(0)

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))


results = {}
for a, c in counts.items():
    if a in results:
        continue
    count = 0
    for aaa, cc in counts.items():
        if a == aaa:
            cc -= 1
        if cc <= 1:
            continue
        if cc <= 2:
            count += 1
            continue
        count += cmb(cc, 2)
    results[a] = int(count)

for k in range(nn):
    print(str(results[aa[k]]))

Submission status: Wrong Answer

Solution code:
import collections
import math
N = int(input())
A = list(map(int, input().split(' ')))
c = collections.Counter(A)
d1 = {}
d2 = {}
for i in c:
    d1[str(i)] = (c[i]*(c[i]-1))/2
    d2[str(i)] = ((c[i]-1)*(c[i]-2))/2

s = sum(d1.values())

print(c)
for i in range(N):
    ans = s - d1[str(A[i])]+d2[str(A[i])]
    print(int(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
import collections
import math
def combinations_count(n, r):
    if(n<=1):
        answer=0
    else:
        answer=math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    return answer

table=collections.Counter(a)
keytable=collections.Counter(a).keys()
c=[]

for key in keytable:
    c.append(table[key])
print(c)
ca=[]
for j in range(len(c)):
    ca.append(combinations_count(c[j], 2))
print(ca)
sums=sum(ca)
print(sum)
print(keytable)
print(table)
for i in range(len(a)):
    keynum=list(keytable).index(a[i])
    answer=sums-ca[keynum]+combinations_count(c[keynum]-1, 2)
    print(answer)

Submission status: Wrong Answer

Solution code:
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(" ")))

    total = 0
    c_list = []
    a_count_list = []
    for i in range(n):
        count = a.count(i + 1)
        a_count_list.append(count)
        # print(count)
        if count > 1: # 2個以上
            c = combinations_count(count, 2)
        else:
            c = 0

        c_list.append(c)
        total = total + c

    print(a, c_list, total, a_count_list)
    for k in range(n):
        if c_list[a[k] - 1] == 1:
            q = 1
        elif c_list[a[k] - 1] == 0:
            q = 0
        else:
            # q = c_list[a[k] - 1] - 1
            q = c_list[a[k] - 1] - c_list[a[k] - 1] * (a_count_list[a[k] - 1] - 2) // a_count_list[a[k] - 1]
        print(total - q)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ap = {}
	for i in A:
		if i in ap:
			ap[i] += 1
		else:
			ap[i] = 1

	mmax = 0
	for k, v in ap.items():
		if v > 1:
			mmax += cmb(v, 2)

	for i in A:
		conts = ap[i]
		conts2 = conts -1
		#print("{} {}".format(conts, conts2))

		p = cmb(conts2, 2)
		m = cmb(conts, 2)
		if conts2 < 2:
			p = 0
		#print("{} {}".format(p, m))
		aaa = mmax - m + p
		print(max(aaa,0))


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
list = list(map(int,input().split()))
list.append(-1)
kosuu = [0] * N
total = 0
listed = sorted(list)
i = 0
count = 1
while i < N:
    a = listed[i]
    if a == listed[i+1]:
        count += 1
    else:
        kosuu[a-1] = count
        total += ( count * (count-1) ) //2
        count = 1
    i += 1
for i in range(N):
    a = kosuu[list[i]-1]
    print(total-a*(a-1)//2 + (a-1)*(a-2)//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted(A)
for k in range(N):
	s=0
	for i in range(N):
		for j in range(i+1,N):
			if B[i]==B[j]:
				s=s+1
			else:
				break
	if B[i]==A[k]:
		s=s-1
	print(s)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


dict_A={}
B=list(set(A))
sum=0


for b in B:
    a=A.count(b)
    sum+=a*(a-1)//2

for a in A:
    print(sum-a+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return (n * (n - 1)) // 2


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
d = {key: choose(value) for key, value in c.items()}
if len(d) > 1:
    sum_d = sum(d.values())
    for a in A:
        print(sum_d - d[a] + (d[a] // 2))
else:
    ans = choose(N - 1)
    for _ in range(N):
        print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
import collections

N = int(input())
BALLS = list(map(int, input().split()))

COUNTS = collections.Counter(BALLS)


MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        return 0
    MEMO[n] = int(comb(n, r))
    return MEMO[n]

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = sum(fact(v if k != n else v - 1) for (k, v) in COUNTS.items())
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
res = list(map(int,input().split()))
a = Counter(res)
k = 0
for i in a.keys():
    a[i] -= 1
    sums = 0
    for j in a.values():
        sums += j * (j - 1) // 2
    a[i] += 1
    res = [sums if x == i else x for x in res]
for k in res:
    print(k)

Submission status: Wrong Answer

Solution code:
def aC(a):
  if a == 0:
    return 0
  return a*(a-1)/2

N = input()
N = int(N)
B = input().split(" ")
A = []
for a in B:
  A.append(int(a))
  
for i in range(0,N):
  pre_A = A[:]
  pre_A.pop(i)
  ans = 0
  count = 0
  for i in range(1,N+1):
    aaa = pre_A.count(i)
    ans = ans + aC(aaa)
    count = count + aaa
    if count == N:
      break
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
s = [int(i) for i in input().split()]

s_set = set(s)

counted = Counter(s)
ans = sum(i*(i-1)/2 for i in counted.values())
print(ans)

for i in s:
    x = counted[i]
    print(int(ans - x + 1))

Submission status: Wrong Answer

Solution code:
import collections
MOD = 10**9+7
n = int(input())
a = list(map(int, input().split()))
b = [[0 for j in range(2)] for i in range(n)]
c = collections.Counter(a)
s = 0
def nCr(nn, r, mod):
	r = min(r, nn-r)
	numer = denom = 1
	for i in range(1, r+1):
		numer = numer * (nn+1-i) % mod
		denom = denom * i % mod
	return numer * pow(denom, mod-2, mod) % mod
for i in c:
	if c[i] < 2:
		b[i-1][0] = 0
	else:
		b[i-1][0] = nCr(c[i],2,MOD)
		s += b[i-1][0]
	if c[i]-1 < 2:
		b[i-1][1] = 0
	else:
		b[i-1][1] = nCr(c[i]-1,2,MOD)
for i in a:
	ans = s-b[i-1][0] + b[i-1][1]
	print (ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))

c = collections.Counter(a)

comon = c.most_common()
ans = 0
for i in comon:
  if i[1] != 1:
  	ans += (i[1]*(i[1]-1)//2)
  
for i in a:
    for j in comon:
      if i == j[0]:
        co = j[1]
        break
    if co == 1:
      print(0)
    else:
      print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def make_cmb_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def cmb(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n = int(input())
    a = list(map(str, input().split()))
    table = make_cmb_table(n)

    d = dict()
    for i in range(n):
        if a[i] in d:
            d[a[i]] = d[a[i]] + 1
        else:
            d[a[i]] = 1

    total = 0
    normal = dict()
    target = dict()
    for k, v in d.items():
        t = cmb(v, 2, table)
        normal[k] = t
        target[k] = cmb(v-1, 2, table)
        total += t

    for i in range(n):
        print(total - normal[a[i]] + target[a[i]])


main()

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

n = int(input())
a = list(map(int,input().split()))
a_s = set(a)
for i in range(n):
    l = a[i]
    a[i] = 'X'
    ans = 0
    for j in a_s:
        ans += comb(a.count(j),2)
    print(int(ans))
    a[i] = l

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
A = list(map(int, input().strip().split()))

q = np.zeros((n+1),dtype=np.int64)
q[2] = 1
q[3] = 3
q[4] = 6
for i in range(5,n+1):
    q[i] = q[i-1] * i

c = np.zeros((n+1),dtype=np.int64)
for a in A:
    c[a] += 1

s = 0
dex = np.where(c>0)
for i in dex[0]:
    s += q[c[i]]
for i in range(n):
    #print(A[i],q[c[A[i]]],q[c[A[i]]-1])
    print(s - q[c[A[i]]] + q[c[A[i]]-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [[] for i in range(N)]
ans = [0]*N
for k, a in enumerate(A):
    a = a - 1
    B[a].append(k)


S = 0
for b in B:
    lenb = len(b)
    if lenb >= 1:
        S += lenb * (lenb-1) / 2

for i, b in enumerate(B):
    for j, k in enumerate(b):
        ans[k] = int(S - (len(b) - 1))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

past_ans = {}

def solve(k, arr):
    tmp_arr = []
    tmp_arr.extend(arr)
    deleted_num = tmp_arr.pop(k)

    # 過去に計算していた場合
    if k in past_ans:
        return past_ans[k]

    # 新しく計算する場合
    set_arr = []
    set_arr = list(set(tmp_arr))
    ans = 0
    for i in set_arr:
        ans += combinations_count(tmp_arr.count(i), 2)
    past_ans[deleted_num] = ans
    return ans

def combinations_count(count, r):
    if count <= 1:
        return 0
    return math.factorial(count) // (math.factorial(count - r) * math.factorial(r))

if __name__ == "__main__":
    n = int(input())
    arr = [int(s) for s in list(input().split())]
    [print(solve(k, arr)) for k in range(n)]

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    N = ir()
    A = np.array(lr(), np.int8)
    iA = np.argsort(A)
    B = A[iA]
    B = np.append(B, 2*10**5+1)
    c = []
    d = []
    e = []
    tmp = 1
    st = 0
    for i in range(N+1):
        if tmp == B[i]:
            st += 1
        else:
            if st > 1:
                c.append(tmp)
                d.append(st)
                e.append(st*(st-1)//2)
            else:
                c.append(tmp)
                d.append(st)
                e.append(0)
            tmp = B[i]
            st = 1
    ans = []
    tmp = 0
    # print(c, d, e)
    for i in range(N):
        if B[i] > c[tmp]:
            tmp += 1
        num = d[tmp]
        plu = 0
        if num > 2:
            plu = (num-1)*(num-2)//2
        ans.append(sum(e)-e[tmp]+plu)
    # print(ans)
    # print(iA)
    iiA = np.argsort(iA)
    for i in range(N):
        print(ans[iiA[i]])
            
resolve()

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())


count = [0]*(N+2)
for i in range(N):
    id = A[i]
    count[id] = count[id]+1

sumN = long(0)
for i in range(N):
    sumN = sumN + long(long(count[i]*(count[i]-1))/2)

#print answer
for i in range(N):
    id = A[i]
    sumz = sumN - (count[id] - 1)
    print(sumz)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 3 * pow(10, 5)  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


n = int(input())
a = [int(i) for i in input().split()] 

count = [0 for _ in range(n+1)]
ans = [0 for _ in range(n+1)]
c = collections.Counter(a)
for i in range(n+1):
    #tmp = a.count(i)
    tmp = c[i]
    count[i] = tmp
    ans[i] = cmb(tmp, 2)
#print(count, ans)
sum_ans = sum(ans)
#print(sum_ans)
for k in range(n):
    #count[k] -= 1
    #print(a[k], count[a[k]])
    #print(cmb(count[a[k]]-1, 2) , cmb(count[a[k]], 2))
    ans = sum_ans + cmb(count[a[k]]-1, 2) - cmb(count[a[k]], 2)
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = [0]*(n+1)
tmp = [0]*(n+1)
for i in a:
    x[i] += 1
ans = 0
for i in range(1, n):
    tmp[i] = (x[i] * (x[i]-1))//2
    ans += tmp[i]
for i in range(1, n+1):
    print(ans - tmp[a[i-1]] + (x[a[i-1]]-1)*(x[a[i-1]]-2)//2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
T = []

for i in range(N):
    flag = 0
    for j in range(len(T)):
        if A[i] == T[j][0]:
            T[j][1] += 1
            flag = 1
            break
    if flag == 0:
        T.append([A[i],1])
T2 = []
for i in range(len(T)):
    T2.append(T[i][1])

print(T)
print(T2)

def hoge(List):
    ans = 0
    for i in range(len(List)):
        ans += (List[i]-1)*List[i]//2
    return ans

for i in range(N):
    for j in range(len(T)):
        if T[j][0] == A[i]:
            T2[j] -= 1
            print(hoge(T2))
            T2[j] += 1
            break

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

N = int(input())
A_list = list(map(int, input().split()))

divided = []
for i in range(N):
    divided.append(A_list.count(i + 1))

ans = 0
for j in divided:
    ans += combinations_count(j, 2)

# print(divided)

for k in range(1, N + 1):
    n = divided[A_list[k - 1] - 1]
    # print(n)
    ans_k = ans
    if n > 1:
        ans_k -= n - 1

Submission status: Wrong Answer

Solution code:
N = int(input())
num = list(map(int, input().split()))
dict = {}
for i in range(0, N):
    if num[i] in dict:
        dict[num[i]] += 1
    else:
        dict[num[i]] = 1
totalNum = 0
for i in range(0, N):
    if i in dict and dict[i] > 1:
        totalNum += (dict[i] * (dict[i] - 1)) / 2
for i in range(0, N):
    if dict[num[i]] > 1:
        print(int(totalNum - dict[num[i]] + 1))
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# D
import collections

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combinations_count(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
N = int(input())
A = list( map(int,input().split()))
c = dict(collections.Counter(A))
su = 0
for i in c.values():
    if (i >= 2):
        su += combinations_count(i, 2)

for i in A:
    if (c[i]  >= 3):
        print(su - combinations_count(c[i],2) + combinations_count(c[i]-1,2))
    elif (c[i] == 2):
        print(su - 1)
    else:
        print(su)

Submission status: Wrong Answer

Solution code:
def aC(a):
  if a == 0:
    return 0
  return a*(a-1)/2

N = input()
N = int(N)
B = input().split(" ")
A = []
for a in B:
  A.append(int(a))
  
for i in range(0,N):
  pre_A = A[:]
  pre_A.pop(i)
  ans = 0
  for i in range(1,N+1):
    ans = ans + aC(pre_A.count(i))
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = input().split()
if len(set(A)) == 1:
    print((len(A) * len(A) - 1) // 2)
    exit()
elif len(set(A)) == len(A):
    print(len(A))
    exit()
dA = {}
for a in A:
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

kA = {}
for a in dA:
    dA[a] = dA[a] * (dA[a] - 1) // 2
    kA[a] = (dA[a] - 1) * (dA[a] - 2) // 2
for a in A:
    print(sum(dA.values()) - dA[a] + kA[a])

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import factorial


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return factorial(n) // (2 * factorial(n - 2))


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
d = {key: choose(value) for key, value in c.items()}
if len(d) > 1:
    sum_d = sum(d.values())
    for a in A:
        print(sum_d - d[a] + (d[a] // 2))
else:
    ans = choose(N - 1)
    for _ in range(N):
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7




n = I()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

L = LI()
cnt = Counter(L)
ret = 0
for i in cnt.values():
    ret += comb(i, 2)
for l in L:
    if cnt[l] < 2:
        print(ret)
    else:
        print(ret - comb(cnt[l], 2) + comb(cnt[l] - 1, 2))

Submission status: Wrong Answer

Solution code:
import collections

N = input()
L = input().split()
C = collections.Counter(L)
I = list(C.keys())
V = list(C.values())

for l in L:
    sum = 0
    for i in range(len(I)):
        if l == I[i]:
            sum += (V[i] - 1) * (V[i] - 2) / 2
        else:
            sum += V[i] * (V[i] - 1) / 2
    print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
dic = {}
d = {}
for i in arr:
    if i not in dic:
        dic[i]=1
    else:
        dic[i]+=1
for i in arr:
    ans=0
    if dic[i]>=2:
        if i not in d:
            for j in dic.keys():
                if i==j:
                    t=dic[j]-1    
                else:t = dic[j]
                ans+=(t*(t-1))//2
            d[i]=ans
        print(d[i])
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import collections
import copy

def f(l):
    return l*(l-1)


n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
print(b)

for x in a:
    c=copy.deepcopy(b)
    c[x]-=1
    d=c.values()
    e=0
    for y in d:
        e+=f(y)
    print(e//2)

Submission status: Wrong Answer

Solution code:
n = input()
n = int(n)
input_list = list(map(int, input().split()))
print(input_list)
dicts = {}
for i in range(n):
    if input_list[i] not in dicts.keys():
        dicts[input_list[i]] = 0
    dicts[input_list[i]] += 1

sums = 0
dicts2 = {}
for key, value in dicts.items():
    if dicts[key] >= 2:
        dicts2[key] = value * (value - 1) // 2
    else:
        dicts2[key] = 0
    sums += dicts2[key]

print(dicts, dicts2)
for j in range(n):
    if dicts[input_list[j]] >= 2:
        value1 = dicts[input_list[j]]
        res = sums - dicts2[input_list[j]] + (value1-1) * (value1 - 2) // 2
    else:
        res = sums
    print(str(res))

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

comb_dic = {}

def combination_formula_MOD(n, r, MOD):
    """nCrを O(min(n-r, r)) で高速に計算する"""
    def _inv(x, MOD):
        """xの逆元を返す"""
        return pow(x, MOD-2, MOD)
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)%MOD
        bunbo = bunbo*(i+1)%MOD

    ans = (bunsi*_inv(bunbo, MOD))%MOD
    comb_dic[(n,r)] = ans
    return ans


def combination_formula(n, r):
    """nCrは、O(min(n-r, r))で実装する
    Notes:
        分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
        求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
    """
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)
        bunbo = bunbo*(i+1)

    comb_dic[(n,r)] = bunsi//bunbo
    return bunsi//bunbo


def solve():
    N = int(input())
    As = list(map(int, input().split()))
    MOD = 10**9+7

    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    calc_dic = {}  # すでに計算済みのもの
    for a in As:
        ans = 0
        if not a in calc_dic:
            for key, value in dic.items():
                if key == a:
                    value -= 1
                # ans += combination_formula(value, 2)
                ans += combination_formula_MOD(value, 2, MOD)
            calc_dic[a] = ans
            print(calc_dic[a])
        else:
            print(calc_dic[a])



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = sorted(map(int,input().split()))
cnt = []
cnt1 = 1
for i in range(1,n):
    if a[i] == a[i-1]:
        cnt1 += 1
        if i == n-1:
            cnt.append(cnt1)
    else:
        cnt.append(cnt1)
        cnt1 = 1
        if i == n-1:
            cnt.append(cnt1)

cnt_s = set(cnt)
cmb_patern = {}

for c in cnt_s:
    if c not in cmb_patern.keys():
        if c >= 3:
            cmb_patern[c] = [combinations_count(c,2), combinations_count(c-1,2)]
        elif c == 2:
            cmb_patern[c] = [1,0]
        else:
            continue

cmb = [0] * len(cnt)

for i in range(len(cnt)):
    if cnt[i] >= 2:
        cmb[i] = cmb_patern[cnt[i]][0]

cmb_all = sum(cmb)

for i in range(len(cnt)):
    if cnt[i] == 1:
        print(cmb_all)
    elif cnt[i] == 2:
        print(cmb_all - 1)
        print(cmb_all - 1)
    else:
        ans = cmb_all - cmb[i] + cmb_patern[cnt[i]][1]
        for j in range(cnt[i]):
            print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 2 * pow(10, 5)  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


n = int(input())
a = [int(i) for i in input().split()] 

count = [0 for _ in range(n+1)]
ans = [0 for _ in range(n+1)]
c = collections.Counter(a)
for i in range(n+1):
    #tmp = a.count(i)
    tmp = c[i]
    count[i] = tmp
    ans[i] = cmb(tmp, 2)
#print(count, ans)
sum_ans = sum(ans)
#print(sum_ans)
for k in range(n):
    #count[k] -= 1
    #print(a[k], count[a[k]])
    #print(cmb(count[a[k]]-1, 2) , cmb(count[a[k]], 2))
    ans = sum_ans + cmb(count[a[k]]-1, 2) - cmb(count[a[k]], 2)
    print(ans)