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 math

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

def list_difference(list1,list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)
    return result

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


for i in range(N):
    target = [A[i]]
    result = list_difference(A,target)
    if len(set(result)) == len(result):
        print(0)
        continue
    else:
        elem = list(set(result))
        count = []
        for j in elem:
            count.append(result.count(j))
        total = []
        for k in elem:
            for l in count:
                try: 
                    a = combination_count(l,2)
                    total.append(a)
                except:
                    a = 0
                    total.append(a)
        print(sum(total))

Submission status: Wrong Answer

Solution code:
import copy
from collections import Counter
from math import factorial

def comb(n,r):
  a = (factorial(n) // factorial(r)) // factorial(n - r)
  return float(a)

N=int(input())
A=list(map(int,input().split() ))
B=[-1]*N   #メモ化。iの時の方法の総数

f_cnt=Counter(A)
f_dic=dict(f_cnt)

for i,item in enumerate(A):
  if B[item-1]>-1:
    print(B[item-1])
  else:
    D=copy.deepcopy(f_dic)
    D[item] -= 1
    opt=0
    for item3 in D:
      if D[item3]>=2:
        opt += comb(D[item3],2)
    B[item-1]=opt
    print(opt)

Submission status: Wrong Answer

Solution code:
import copy
import collections
import math
import sys

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

N = int(input())
A = [int(i) for i in input().split()] 

bigC = collections.Counter(A)

maxnum = max(A)
lis = [-1] * maxnum
for i, a in enumerate(A):
  if lis[a-1] < 0:
    z = bigC[a-1]
    bigC[a-1] -= 1
    c = bigC
    total = 0
    for idx in c:
      total += combinations_count(c[idx], 2)
      
    lis[a-1] = total
    for x in bigC:
      if bigC[x] == bigC[a]:
        lis[x-1] = total
    print(total)
    bigC[a-1] += 1
  else:
    print(lis[a-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

from operator import mul
from functools import reduce
from functools import lru_cache

N = int(input())
A_list = [int(e) for e in input().split()]

#ある番号のボールが何個あるかをまとめる
number_dict = dict()

for i in range(N):
    ball_number = A_list[i]
    if ball_number not in number_dict:
        number_dict[ball_number] = 0
        
    number_dict[ball_number] += 1

#それぞれの番号のボールから2個選ぶ組み合わせをカウントする。
comb_dict = dict()

@lru_cache(maxsize=10000000000000)
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
    
@lru_cache(maxsize=10000000000000)
def two_choice(N):
    if N == 2:
        return 1
    elif N <= 1:
        return 0
    elif N == 3:
        return 3
    else:
        return combinations_count(N,2)*combinations_count(N-2,2)

all = 0

for in_dict in number_dict.items():
    ball_number = in_dict[0]
    balls = in_dict[1]
    comb_dict[ball_number] = two_choice(balls)
    all += comb_dict[ball_number]

#回答作成
for i in range(1,N+1):
    ball_number = A_list[i-1]
    now_balls = number_dict[ball_number] - 1
    print(int(all-comb_dict[ball_number]+two_choice(now_balls)))

Submission status: Wrong Answer

Solution code:
import collections

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
    
n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)    
s = list(set(li))
ans = 0
d = collections.defaultdict(int)

for j in range(len(s)):
    if c[s[j]] <= 1:
        continue
    ans += combination(c[s[j]], 2)

for i in range(n):
    if d[li[i]] == 0:
        ans_a = ans
        if c[li[i]] <= 1:
            print(ans_a)
            d[li[i]] = ans_a
            continue
        ans_a -= combination(c[li[i]], 2)
        c[li[i]] -= 1
        if c[li[i]] <= 1:
            print(ans_a)
            c[li[i]] += 1
            d[li[i]] = ans_a
            continue
        ans_a += combination(c[li[i]], 2)
        c[li[i]] += 1
        d[li[i]] = ans_a
        print(ans_a)
    else:
        print(d[li[i]])

Submission status: Wrong Answer

Solution code:
l = int(input())
A = input().split(" ")

unique = set(A)

def combination(number):
  if number == 0 or number == 1:
    return 0
  else:
    return int(number * (number - 1) / 2)

def caluculate(string):
  if memo[string] == 0:
    return(0)
  if memo[string] == 1:
    return(1)
  else:
    return(memo[string] - 1) 
  
total = 0
memo = {}
for i in unique:
  times = A.count(i)
  memo[i] = times
  total += combination(times)

# print(memo)
# print(memo.keys())
# print(total)

for i in A:
  #  print(caluculate(i))
  print(total - caluculate(i))

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 + 1):
    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:
from collections import defaultdict


def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

dd = defaultdict(int)
for i in range(N):
    dd[A[i]] += 1

count = 0
for k, v in dd.items():
    if v >= 2:
        count += nCr(v, 2)
for i in range(N):
    if dd[A[i]] >= 3:
        ans = count - nCr(dd[A[i]], 2) + nCr(dd[A[i]]-1, 2)
    elif dd[A[i]] == 2:
        ans = count - 1
    else:
        ans = count
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=list(map(int,input().split()))
print(k)
for i in range(n):
    x=k.pop(i)
    ans=0
    for j in range(n):
        c=k.count(j)
        ans=ans+c*(c-1)//2
    print(ans)
    if i!=n-1:
        k.insert(i,x)
    else:
        k.append(x)

Submission status: Wrong Answer

Solution code:
import math

def countComb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

#p = 10 ** 9 + 7
p = 2147483647
NN = 10 ** 6  # N は必要分だけ用意する
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, NN + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

memo = [0 for _ in range(N)]
for a in A:
  memo[a-1] += 1

memo1 = [0 for _ in range(N)]
for n in range(N):
  memo1[n] = countComb(memo[n], 2, p)

total = sum(memo1)
for k in range(N):
  a = A[k]-1
  answer = 0
  answer += total
  answer -= memo1[a]
  answer += countComb(memo[a] - 1, 2, p)
  print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
c = Counter(a)
d = {}
for k, v in list(c.items()):
    if v < 2:
        del c[k]
if len(c) == 1:
    b = list(c)[0]
    for i in range(n):
        print(b * 2)
else:
    for i in range(n):
        b = {k: count for k, count in c.items() if k != a[i]}
        print(sum(b.values()))

Submission status: Wrong Answer

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

def checkPatternNum(inA):
    totalCount = 0
    while(len(inA) > 0):
        targetCount = inA.count(inA[0])
        if(2 <= targetCount):
            for n in range(targetCount+1):
                if(n > 1):
                    totalCount += (n-1)
        targetData = inA[0]
        inA = [s for s in inA if s != targetData]
    return totalCount

for index in range(N):
    targetA = A.copy()
    del targetA[index]
    print(checkPatternNum(targetA))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
a = list(map(int,input().split()))
b = collections.Counter(a)
c = list()
for i in range(1,n+1):
    c.append(int((b[i]*(b[i]-1))/2))
print(c)
for i in range(n):
    d = int(a[i]-1)
    if c[d]>2:
        e = sum(c) - c[d] + int( (c[d])*(b[d+1]-2) /(b[d+1]) )
    else:
        e = sum(c) - c[d]
    print(e)

Submission status: Wrong Answer

Solution code:
def fact(n, end=1):
  if n <= end: return 1
  return n * fact(n-1, end=end)
def comb(a, b):
  if a < b:
    return 0
  return fact(a, end=a-b) / fact(b)
N = int(input())
A = list(map(int, input().split()))
dp = [[0, 0] for i in range(N+1)]
for i in range(N):
  dp[A[i]][0] += 1
x = 0
for i in range(N):
  dp[i][1] = comb(dp[i][0], 2)
  x += dp[i][1]
for i in range(N):
  y = comb(dp[A[i]][0]-1, 2)
  print(int(x - dp[A[i]][1] + y))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
def comb(n,r):
    if n - r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def choose_ball(num, nums):
    count = 0
    for i in nums:
        if num == i:
            count += comb(nums[i]-1,2)
        else:
            count += comb(nums[i],2)
    return count

N = int(input())
A = list(map(int,input().split()))
nums = {}
for num in A:
    if not num in nums:
        nums[num] = 1
    else: 
        nums[num] += 1
print(nums)
for num in A:
    print(choose_ball(num, nums))

#1 1 1 2

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


l = int(input())
A=list(map(int, input().split()))
S = Counter(A)

for i in A:
  tmp = []
  S[i] -= 1
  for j in S.keys():
    tmp.append(cmb(S[j],2,mod))
  S[i] += 1
  print(sum(tmp))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int, input().split()))
dic = {}
ans = 0
a = 0

for i in range(n):
  a = l.count(i+1)
  if a == 0 or a == 1:
    if max(l) < i:
      break
    else:
      continue
  else:
    dic[i+1] = a
    x = l.count(i+1)
    ans += int(x*(x-1)/2)
  
for i in range(n):
  if dic.get(l[i]) != None:
    a = dic[l[i]]
    print(ans-a+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = input().split()
AA = A
for i in range(N):
    r = 0
    x = AA.pop(i)
    y = Counter(AA)
    a = y[1]
    b = y[2]
    c = y[3]
    d = y[4]
    e = y[5]
    f = y[6]
    g = y[7]
    h = y[8]
    o = y[9]
    p = y[0]
    print((a*(a-1)+b+(b-1)+c*(c-1)+d*(d-1)+e*(e-1)+f*(f-1)+g*(g-1)+h*(h-1)+o*(o-1)+p*(p-1))/2)
    AA.insert(i,x)
    print(int(r))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

from operator import mul
from functools import reduce
from functools import lru_cache
import math

N = int(input())
A_list = [int(e) for e in input().split()]

#ある番号のボールが何個あるかをまとめる
number_dict = dict()

for i in range(N):
    ball_number = A_list[i]
    if ball_number not in number_dict:
        number_dict[ball_number] = 0
        
    number_dict[ball_number] += 1

#それぞれの番号のボールから2個選ぶ組み合わせをカウントする。
comb_dict = dict()

@lru_cache(maxsize=100000000)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
@lru_cache(maxsize=100000000)
def two_choice(N):
    if N == 2:
        return 1
    elif N <= 1:
        return 0
    elif N == 3:
        return 3
    else:
        return combinations_count(N,2)*combinations_count(N-2,2)

all = 0

for in_dict in number_dict.items():
    ball_number = in_dict[0]
    balls = in_dict[1]
    comb_dict[ball_number] = two_choice(balls)
    all += comb_dict[ball_number]

#回答作成
for i in range(1,N+1):
    ball_number = A_list[i-1]
    now_balls = number_dict[ball_number] - 1
    print(all-comb_dict[ball_number]+two_choice(now_balls))

Submission status: Wrong Answer

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

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

for key in keytable:
    c.append(table[key])
#print(c)
ca=[]
for j in range(len(c)):
    ca.append(c[j]*(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]+(c[keynum]-1)*(c[keynum]-2)/2
    print(int(answer))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in a:
    a_ = a[:i]+a[i+1:]
    s = set(a_)
    l = []
    for s_ in s:
        n = a_.count(s_)
        l.append(int(n*(n-1)/2))
    print(sum(l))

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
tmp = {}
for i in range(n):
    if a[i] in tmp:
        print(tmp[a[i]])
    else:
        a_copy = a[:]
        a_copy.remove(a[i])
        c = collections.Counter(a_copy)
        cnt = 0
        for i in c.values():
            cnt += i * (i-1) // 2
    
        tmp[a[i]] = cnt
    
        print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
ndarr = np.array(A)

def num2len(n):
	return np.count_nonzero(ndarr == n)
  

def main():
	print(*[num2len(a) for a in A], sep="\n")
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
N=int(input())
A=list(map(int,input().split()))
for j in range(1,N+1):
    B=A[:j-1]+A[j:]
    print(int(sum([comb(B.count(i),2) for i in range(1,N+1)])))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(input().split())

a_dict = dict()
for x in a:
    if x not in a_dict:
        a_dict[x] = 1
    else:
        a_dict[x] += 1

sum = 0
for k, v in a_dict.items():
    print(v)
    print((v-2)/v)
    sum += v*(v-1)//2
    a_dict[k] = (v*(v-1)//2)-((v-1)*(v-2)//2)

for i in a:
    print(int(sum-a_dict[i]))

Submission status: Wrong Answer

Solution code:
from collections import Counter

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

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

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

memo = {}
for i in range(n):
    num = A[i]
    if num in memo:
        print(memo[num])
    else:
        t = counter[num]
        ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
        print(ans)
        memo[num] = ans

Submission status: Wrong Answer

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

#output
from collections import  Counter
L = Counter(A)
M = len(L)

original_answer = 0
for i in range(1, N):
    if L[A[i]] >= 2:
        original_answer += L[i] * (L[i]-1) // 2

for i in range(N):
    temp = 0
    if L[A[i]] == 2:
        temp -= 1
    elif L[A[i]] > 2:
        temp = temp - L[A[i]]*(L[A[i]]-1)//2 + (L[A[i]]-1)*(L[A[i]]-2)//2 
    print(original_answer + temp)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

ans_dict = {}
ans_keys = []
value_dict = {1: 0}
value_keys = [1]
for i in range(n):
    num = a_list[i]
    if num in ans_keys:
        print(ans_dict[num])
    else:
        buff = a_list[:i]
        buff.extend(a_list[i+1:])
        c = Counter(buff)

        tmp_ans = 0
        for value in c.values():
            if value in value_keys:
                tmp_ans += value_dict[value]
            else:
                tmp = (value * (value - 1))/2
                tmp_ans += tmp
                value_dict[value] = tmp
                value_keys.append(value)
        ans_dict[num] = tmp_ans
        ans_keys.append(num)
        print(int(tmp_ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted([x for x in set(a) if a.count(x)>1], key=a.index)
c=[a.count(i) for i in b]
ans=0
for i in c:
    ans+=((i-1)*i)//2

cnt=ans   
for i in range(n):
   if a[i] in b:
       ans-=c[b.index(a[i])]
       print(ans+1)
       ans=cnt
   else:
       print(ans+1)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
N=int(input())
A=list(map(int,input().split()))
for j in range(1,N+1):
    print(int(sum([comb((A[:j-1]+A[j:]).count(i),2) for i in range(1,N+1)])))

Submission status: Wrong Answer

Solution code:
n = int(input())
aList = list(map(int, input().split()))
acount = [aList.count(i)-1 for i in aList]
sums = sum(acount)
for i in acount:
    print((sums)//2 - i for i in acount)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
MOD=10**9+7
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
comb=Combination(2*10**5)
d=Counter(a)
tni=0
dv=d.values()
dv=list(dv)
for i in range(len(dv)):
    tni+=comb(int(dv[i]),2)

for i in range(n):
    r=d[a[i]]
    print(tni-(r-1))

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 in comb_dic:
        return comb_dic[n]

    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] = ans
    return ans


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

    if n in comb_dic:
        return comb_dic[n]

    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] = bunsi//bunbo
    return comb_dic[n]


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

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


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
a=0
list1 = list(map(int, input().split()))
c = collections.Counter(list1)
for i in range(N):
    a+=int(c[i+1]*(c[i+1]-1)/2)
for i in range(N):
    print(a-c[list1[i]]*2+3)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

a = list(set(A))
cc = Counter(A)
dup = [x for x in a if cc[x] > 1]
m = len(a)
l = len(A) 
al = sum(cc.values())

for k in A:
    if k in dup:
        print(int(al-cc[k]+1))
    else :
        print(int(al))

Submission status: Wrong Answer

Solution code:
import numpy as np

def balls(t):
  hoge = 0
  for i in range(t):
    hoge += 1+i
  return hoge

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

unique_A_list = list(set(A_list))
unique_A = np.c_[list(set(A_list))]
ones_minus = np.c_[-1 * np.ones((len(unique_A)), int)]

np_A = np.array(unique_A)
ans_dict = dict(np.concatenate([np_A, ones_minus], 1))
num_dict = dict(np.concatenate([np_A, ones_minus], 1))

print(unique_A_list)
for i in unique_A_list:
  num_dict[i] = sum(x == i for x in A_list)
  
for i in unique_A_list:
  num_dict[i] = num_dict[i] - 1
  hoge = 0
  for j in unique_A_list:
    hoge += balls(num_dict[j]-1)
  ans_dict[i] = hoge
  num_dict[i] = num_dict[i] + 1
  
for i in A_list:
  print(ans_dict[i])

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
A = list(map(int, input().split(' ')))


def main(n: int, a: list):
    counter = collections.Counter(a)
    pairs = {k: v * (v - 1) / 2 for k, v in counter.items()}
    pairs_all = sum(pairs.values())

    print(pairs)

    counted = {}

    for i in range(N):

        k = a[i]
        v = counter[k] - 1
        # print(pairs_all, pairs[k], v)
        pair_cnt = pairs_all - pairs[k] + (v*(v-1)/2)

        # if target not in counted.keys():
        #     temp = pairs.copy()
        #
        #     v = counter[target] - 1
        #     temp[target] = v * (v - 1) / 2
        #
        #     pair_cnt = sum(temp.values())
        #     counted.update({target: pair_cnt})
        # else:
        #     pair_cnt = counted[target]
        print(int(pair_cnt))


main(N, A)

Submission status: Wrong Answer

Solution code:
import copy

N=int(input())

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

#print(A)

mama=dict()
papa=dict()
papa[0]=0
papa[1]=0
papa[2]=1
for i in range(3,N):
    papa[i]=i*papa[i-1]
for i in range(N):

    if(A[i] in mama):
        print(mama[A[i]])
        continue
    
    AA=copy.deepcopy(A)
    ai=A[i]
    del AA[i]
    #print(AA)
    Aset=set(AA)
    count=0
    
    for i in Aset:
        aa=AA.count(i)
        if(aa in papa):
            count+=papa[aa]
            continue
        #print(i,aa)
        aiu=int((aa*(aa-1))/2)
        count+=aiu
        papa[aa]=aiu
    print(count)
    mama[ai]=count

Submission status: Wrong Answer

Solution code:
def fact(n, end=1):
  if n <= end: return 1
  return n * fact(n-1, end=end)
def comb(a, b):
  if a < b:
    return 0
  return fact(a, end=a-b) / fact(b)
N = int(input())
A = list(map(int, input().split()))
an = [0 for i in range(N+1)]
av = [0 for i in range(N+1)]
for i in range(N):
  an[A[i]] += 1
for i in range(N):
  av[i] = comb(an[i], 2)
x = sum(av)
for k in range(N):
  y = comb(an[A[k]]-1, 2)
  print(int(x - av[A[k]] + y))

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
c=list(map(int,input().split()))

s = Counter(c)
t = list(s.items())

nag = len(t)
x = 0
rt = [0 for i in range(nag)]
print(s)

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
for f in range(nag):
    rt[f] = x - (t[f][1] -1)
  
for j in range(n):
    for k in range(nag):
        if c[j] == t[k][0]:
            print(rt[k])
            break

Submission status: Wrong Answer

Solution code:
from collections import Counter

k = int(input())
a = list(map(int, input().split()))

for i in range(k):
    b = 0
    x = a.pop(a[i])
    count = Counter(a)
    a.insert(i, x)
    x = ""
    for k,v in count.items():
        if v == 1:
            b += 0
        else:
            b += v * (v-1) / 2
    print(int(b))

Submission status: Wrong Answer

Solution code:
def npr(x,x1):
    l=[1,1,1]
    a=1
    for i in range(2,x+1):
        a*=i
        if i==x1:
            l[0]=a
        if i==x-x1:
            l[1]=a
    l[2]=a 
    return l[2]//(l[0]*l[1])
n=int(input())
l=list(map(int,input().split()))
d={}
d1={}
ans=0
for i in l:
    if i not in d:
        d[i]=1
    else:
        d[i]+=1
for i in d.keys():
    x=npr(d[i],2)
    d1[i]=x
    ans+=x
for i in l:
    if d[i]>2:
        print(ans-d1[i]+(d1[i]*(abs(d[i]-2))//d[i]))
    elif d[i]==2:
        print(ans-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import collections
import math
import sys

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

N = int(input())
A = [int(i) for i in input().split()] 

bigC = collections.Counter(A)
vals = list(bigC.values())
if sum(vals) == N and vals[0] == 1:
  for _ in range(N):
    print(0)
  sys.exit()

maxnum = max(A)
lis = [-1] * maxnum
for i, a in enumerate(A):
  if lis[a-1] < 0:
    newA = copy.deepcopy(A)
    newA.pop(i)
    c = collections.Counter(newA)
    total = 0
    for idx in c:
      total += combinations_count(c[idx], 2)
      
    lis[a-1] = total
    for x in bigC:
      if bigC[x] == bigC[a]:
        lis[x-1] = total
    print(total)
  else:
    print(lis[a-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
aList = list(map(int, input().split()))
acount = []
for i in aList:
    acount.append(aList.count(i)-1)
sums = sum(acount)
for i in acount:
    print((sums)//2 - i for i in acount)

Submission status: Wrong Answer

Solution code:
import copy
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def D159():
    N = int(input())
    A = input().split()
    #sum = 0
    for i in range(0, N):
        sum = 0
        A_ = copy.deepcopy(A)
        del A_[i]
        num = list(set(A_))
        for j in num:
            if A_.count(j) > 1:
                sum += combinations_count(A_.count(j), 2)
        print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
balls = input().split()
for j in range(n):
  ans = 0
  len_n = 0
  for k in range(n):
    cont = balls.count(str(k))
    if len_n + cont >= n:
      break
    if balls[j] == str(k):
      ans += (cont - 1) * (cont - 2) / 2
    else:
      ans += cont * (cont - 1) / 2
  print(int(ans))

Submission status: Wrong Answer

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

cnt_list = [0]*(N+1)
for i in range(1,N+1):
  cnt_list[i] = A.count(i)

print(cnt_list)

result = 0
for i in range(1,N+1):
  result += cnt_list[i] * (cnt_list[i]-1) * (1/2)

res = int(result)
for i in range(0,N):
  print(res-cnt_list[A[i]]+1)

Submission status: Wrong Answer

Solution code:
def comb(n, r):
    bunshi = 1
    for i in range(n-r+1,n+1):
        bunshi = bunshi*i
    bunbo = 1
    for i in range(1,r+1):
        bunbo = bunbo * i 
    return bunshi//bunbo

def pascal(n):
    c = [[0 for i in range(n+1)] for j in range(n+1)]
    c[0][0] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j == 0 or j == i:
                c[i][j] = 1
                continue
            c[i][j] = c[i-1][j-1] +c[i-1][j]
    return(c)

def nC2(n):
    c = [0 for _ in range(n)]
    c[0] = 1
    for i in range(1, n):
        c[i] = i+1 +c[i-1]
    return(c)

N = int(input())
A = list(map(int, input().split()))
# c = pascal(N)
nc2 = nC2(N)
duplication = {}
ans = 0
for x in A:
    if x in duplication:
        continue
    count = A.count(x)
    if count > 0:
        duplication[x] = count
        # ans += comb(count,2)
        ans += nc2[count-2]
for x in A:
    if x not in duplication:
        print(ans)
    else:
        # print(ans -comb(duplication[x],2) +comb(duplication[x]-1,2))
        print(ans -duplication[x]+1)
        # print(ans -c[duplication[x]][2] +c[duplication[x]-1][2])

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = list(map(int, input().split()))

print(nums)

values = {}
for i in nums:
  if i in values: values[i] += 1
  else: values[i] = 1

sums={} # 各値ごとの組み合わせ数
subsums={} # 各値ごとの組み合わせ数（ボールがないとき版
allsum = 0
for k,v in values.items():
  sums[k] = v * (v - 1) / 2
  undersum = (v - 2) * (v - 1) / 2 if v > 1 else 0
  subsums[k] = sums[k] - undersum
  allsum += sums[k]

# res={} # 各値のない時版 + 他の合計
# for k,v in sums.items():

for i in nums:
  print(int(allsum - subsums[i]))