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: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vector<int> vec(n);
    map<int, pair<int, int>> mp;
    int total = 0;
    rep(i, n) {
        int x; cin >> x;
        total -= mp[x].second;
        vec[i] = x;
        int num = mp[x].first+1;
        mp[x] = make_pair(num, num*(num-1)/2);
        total += mp[x].second;
    }
    rep(i, n) {
        int num = vec[i];
        int ans = total;
        ans -= mp[num].second;
        ans += (mp[num].first-1)*(mp[num].first-2)/2;
        cout << ans << endl;
    }
}

Submission status: Runtime Error

Solution code:
from collections import Counter
import math
def comb(n, r):
    # print(n, r)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
combination = Combination(n-1)

# All combination
total = 0
for (key, val) in c.items():
    # print('\n', key, val)
    total += comb(val, 2)

# print('all:', total)

for i in range(n):
    num = a[i]
    org = c[num]

    # total - orgC2 + (org-1)C2
    if org > 2:
        ans = total - comb(org, 2) + comb(org-1, 2)
    else:
        ans = total - comb(org, 2)
    print(ans)


'''
5
1 1 2 1 2
'''

Submission status: Runtime Error

Solution code:
import collections
import math

def C(n, r):
    if n-r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
#d = {}
d = [-1]*100000
sm = 0
for k,v in c.most_common():

    d[k] = v
    sm += C(v,2)

for a in A:
    print (sm - C(d[a],2) + C(d[a]-1,2) )

Submission status: Runtime Error

Solution code:
n=input()
t=map(int,raw_input().split())
l=[0]*(pow(10,5)+1)
for i in t:
    l[i]+=1
s=0
for x in l:
    s+=(x*(x-1))/2
for x in t:
    a=l[x]
    print s- (a*(a-1))/2 + (a-1)*(a-2)/2

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    if dict.get(a[i],False):
        dict[a[i]]+=1
    else:
        dict[a[i]]=1

for i in range(n):
    sum=0
    for j in dict:
        if j==a[i]:
            if dict[j]>2:
                sum+=((dict[j]-1)*(dict[j]-2))//2
        else:
            if dict[a[j]]>=2:
                sum += ((dict[j])*(dict[j]-1))//2
    print(sum)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
An = [int(x) for x in input().split()]

for i in range(N):
    tmp = copy.copy(An)
    tmp.pop(i)
    
    c = 0
    for i in range(N):
        k = tmp.count(i)
        if k>1:
            c += int(math.factorial(k) / (math.factorial(k-2) * 2))
    print(c)

Submission status: Runtime Error

Solution code:
def cmb(n, k, mod):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % mod

    return (numerator * pow(denominator, mod - 2, mod)) % mod


import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))
freq = {}
for i in a:
    if i in freq:
        freq[i] += 1
    else:
        freq[i] = 1

inf = 1001001001
dp = [inf for _ in range(10005)]
dp2 = [inf for _ in range(10005)]
mod = 10**9 + 7

base = 0
for k, v in freq.items():
    dp[k] = cmb(v, 2, mod)
    dp2[k] = cmb(v - 1, 2, mod)
    base += dp[k]

# print(dp)

for i in a:
    print(base - dp[i] + dp2[i])

# for i in a:
#     if dp[i] == inf:
#         dp[i] = cmb(freq[i],2,mod)
#     print(dp[i])

Submission status: Runtime Error

Solution code:
from collections import Counter
from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
for v in c.values():
    all_comb += v*(v-1)/2

for i in range(n):
    tmp = c[a[i]]
    print(all_comb - 2*(tmp-1))

Submission status: Runtime Error

Solution code:
from math import factorial

N = int(input())
nums = list(map(int, input().split()))
numsB = nums[:]
d = dict()

for num in nums:
    if num not in d:
        d[num] = 1
    else:
        d[num] += 1

total = 0
for i in d:
    n = d[i]
    if n == 2:
        total += 1
    elif n > 2:
        total += factorial(n) / factorial(2) / factorial(n - 2)

for num in numsB:
    tmp = d[num] - 1
#    if tmp >= 2:
#        hoge = factorial(tmp) / factorial(2) / factorial(tmp - 2)
    print(int(total - tmp))

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
d = {}
ans = 0
for _ in range(n):
    a.append(int(input()))
for i in a:
    d[i] = d.get(i,0) + 1
for key in d:
    ans += d[key]*(d[key]-1)//2
for i in a:
    print(ans + 1 - d[i])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
dic = {}
for i in a:
    s.add(i)
    if i in dic:
        dic[i] +=1
    else:
        dic[i] = 1

ans = 0
for i in dic.values():
    ans += i * (i - 1) // 2

for i in a:
    sa = dic[i] * (dic[i] - 1) // 2 - ((dic[i] - 1) * (dic[i] - 2) // 2)
    print(ans - sa)

Submission status: Runtime Error

Solution code:
import collections
import numpy as np

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

di = collections.Counter(li)
#print(di)

arr = np.array(list(di.values()))
arrr = arr - 1
c = np.dot(arr, arrr) // 2
#print(c)

for v in li:
    x = int(di[v])
    if x == 1:
        print(c)
    else:
        print(c-(x-1))
    
#(n * n-1)-(n-1 * n-2) / 2

Submission status: Runtime Error

Solution code:
from math import *
def printNcR(n, r): 
    p = 1
    k = 1
    if (n - r < r): 
        r = n - r 
  
    if (r != 0):  
        while (r): 
            p *= n 
            k *= r  
            m = gcd(p, k)
            p //= m 
            k //= m 
            n -= 1
            r -= 1 
  
    else: 
        p = 1
    return p



n = int(input())
arr = list(map(int, input().split()))
dic = {}
for i in arr:
	if i not in dic:
		dic[i] = 1
	else:
		dic[i]+=1
#print(dic)
for i in range(n):
	count = 0
	for key,val in dic.items():
		if key == arr[i]:
			if val-1 <= 1: continue
			count += printNcR(val-1,2)
		else:
			if val <= 1:
				continue
			else:
				count += printNcR(val,2)
	print(count)

Submission status: Runtime Error

Solution code:
from math import factorial

N = int(input())
nums = list(map(int, input().split()))
d = dict()

for num in nums:
    if num not in d:
        d[num] = 1
    else:
        d[num] += 1

total = 0
for i in d:
    n = d[i]
    if n == 2:
        total += 1
    elif n > 2:
        total += factorial(n) / factorial(2) / factorial(n - 2)

for num in nums:
    tmp = d[num] - 1
#    if tmp >= 2:
#        hoge = factorial(tmp) / factorial(2) / factorial(tmp - 2)
    print(total - tmp)

Submission status: Runtime Error

Solution code:
import copy
import itertools
from scipy.special import comb

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

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

for k in range(1, N + 1):
    tmp_divided = copy.deepcopy(divided)
    tmp_divided[A_list[k - 1] - 1] -= 1

    ans = 0
    for j in tmp_divided:
        ans += comb(j, 2)

    print(int(ans))

Submission status: Runtime Error

Solution code:
import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))

d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1
history = dict()
history[0] = 1
history[1] = 1
history[2] = 2
def stepMulti(v):
    if v < 1:
        return 1
    if v not in history:
        history[v]  = v * stepMulti(v-1)
    return history[v]

def C(a,b):
    return stepMulti(a) // (stepMulti(a-b) * stepMulti(b))

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        d[one] -= 1
        res = 0
        for k,v in d.items():
            if v==2:
                res += 1
            elif v > 2:
                res += C(v, 2)
        print (res)
        d[one] += 1
        res_history[one] = res

Submission status: Runtime Error

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

c = dict(Counter(a))
dp_on = {}
dp_off = {}
for k, v in c.items():
if v < 2:
        dp_on[k] = 0
        dp_off[k] = 0
elif v < 3:
        dp_on[k] = 1
        dp_off[k] = 0
else:
        dp_on[k] = int(v*(v-1)/2)
        dp_off[k] = int((v-1)*(v-2)/2)
comb_sum = sum([v for v in dp_on.values()])
for i in range(n):
print(comb_sum - dp_on[a[i]] + dp_off[a[i]])

Submission status: Runtime Error

Solution code:
N = int(input().strip())
A = [int(v) for v in input().strip().split()]
C = {}
S = {}

for a in A:
    C.setdefault(a, 0)
    C[a] += 1

for c in C.values():
    if c < 1:
        continue
    C.setdefault(c, c * (c - 1) // 2)
    if c < 2:
        continue
    C.setdefault(c - 1, c * (c - 1) // 2)

for i, a in enumerate(A):
    C[a] -= 1
    sum_ = sum([S[n] for n in C.values() if n > 1])
    C[a] += 1
    print(sum_)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
d = {}
s_sum = {}
s = list(set(l))
for i in range(len(s)):
    d[s[i]] = l.count(s[i])
for i in range(len(l)):
    if l[i] in s_sum:
        print(s_sum[l[i]])
    else:
        ans = 0
        e = copy.deepcopy(d)
        e[l[i]] -= 1
        for v in e.values():
            if v > 1:
                ans += math.factorial(v) // math.factorial(v -
                                                           2) // math.factorial(2)
        s_sum[l[i]] = ans
        print(ans)

Submission status: Runtime Error

Solution code:
M=int(input())
N=list(input().split())
print(N)
check=[0,0,0,0,0,0,0,0,0,0]
for i in range(M):
    check[int(N[i])]+=1
num=0
for i in range(M):
    num+=check[i]*(check[i]-1)//2
for i in range(M):
    print(num-(check[int(N[i])]-1))

Submission status: Runtime Error

Solution code:
from math import factorial

N = int(input())
nums = list(map(int, input().split()))
d = dict()

for num in nums:
    if num not in d:
        d[num] = 1
    else:
        d[num] += 1

total = 0
for i in d:
    n = d[i]
    if n == 2:
        total += 1
    elif n > 2:
        total += factorial(n) / factorial(2) / factorial(n - 2)

for num in nums:
    tmp = d[num] - 1
#    if tmp >= 2:
#        hoge = factorial(tmp) / factorial(2) / factorial(tmp - 2)
    print(int(total - tmp))

Submission status: Runtime Error

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

for i in a:
  count = 0
  a.pop(i)
  for j in a:
    if i == j:
      count += 1
  a.append(i)
  print(count)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

from math import factorial

N = int(input())
nums = list(map(int, input().split()))
d = defaultdict(int)

for num in nums:
    d[num] += 1

total = 0
for i in d:
    n = d[i]
    if n == 2:
        total += 1
    elif n > 2:
        total += factorial(n) / factorial(2) / factorial(n - 2)

for num in nums:
    tmp = d[num] - 1
#    if tmp >= 2:
#        hoge = factorial(tmp) / factorial(2) / factorial(tmp - 2)
    print(int(total - tmp))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
def comb(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

for i in range(N):
    cnt = 0
    arr = copy.copy(A)
    arr.pop(i)
    c = collections.Counter(arr)
    for j in range(N):
        if c[j] >= 2:
           cnt += comb(c[j],2)
    print(cnt)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=500010;



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n;
	cin>>n;
	ll ar[n];
	ll ch[n+1]={0};
	for(ll i=0;i<n;++i){
        cin>>ar[i];
        ch[ar[i]]+=1;
	}

	ll ans=0;
	for(ll i=1;i<=n;++i){
        ll c=(ch[i]*(ch[i]-1))/2;
        if(ch[i]>1)
        {ans=ans+c;}
	}

	for(ll i=0;i<n;++i){
        ll x=ar[i];
        ll c,d;
        if(ch[x]>1){
            c=(ch[x]*(ch[x]-1))/2;
            //cout<<c<<" ";
            ans-=c;
        }
        if(ch[x]>2){
            d=((ch[x]-1)*(ch[x]-2))/2;
            //cout<<d<<endl;
            ans+=d;
        }
        cout<<ans<<endl;
        if(ch[x]>2){ans-=d;}
        if(ch[x]>1){
            ans+=c;
        }
	}

	return(0);
}

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import Counter

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

C = Counter(A)

D = np.zeros(N).astype(int)
D -= 1
for i in A:
    if D[i] != -1:
        print(D[i])
        continue
    C[i] -= 1
    res = 0
    for value in C.values():
        res += value * (value - 1) // 2
    C[i] += 1
    D[i] = res
    print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ac = Counter(A)
comblist = [0 for i in range(max(ac.values())+1)]
comblist[2] = 1
for i in range(3,max(4,max(ac.values())+1)):
    comblist[i] = comblist[i-1]*i//(i-2)
ans = {}
anssum = 0
for k,v in ac.items():
    if v > 1:
        anssum += comblist[v]
    if k not in ans:
        if v == 2:
            ans[k] = -1
        elif v == 1:
            ans[k] = 0
        else:
            ans[k] = comblist[v-1] - comblist[v]
for i in A:
    print(anssum+ans[i])

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

from math import factorial
def comb(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)

dicts = {}

N=one_int()

A = many_int()

# 辞書作成
for a in A:
    if a in dicts:
        dicts[a] += 1
    else:
        dicts[a] = 1

# 2個選ぶ組み合わせ計算
dicts_less ={}
sums = 0
for k, v in dicts.items():
    if v>=2:
        sums += comb(v,2)
    if v<2:
        dicts_less[k]=0
    elif v<=2:
        dicts_less[k]=comb(v,2) - 0
    else:
        dicts_less[k]=comb(v,2) - comb(v-1,2)

for a in A:
    print(int(sums - dicts_less[a]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

from math import factorial

N = int(input())
nums = list(map(int, input().split()))
d = defaultdict(int)

for num in nums:
    d[num] += 1

#print(d)

total = 0
for i in d:
    n = d[i]
    if n >= 2:
        total += factorial(n) / factorial(2) / factorial(n - 2)

for num in nums:
    tmp = d[num] - 1
    if tmp >= 2:
        hoge = factorial(tmp) / factorial(2) / factorial(tmp - 2)
    print(int(total - tmp))

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
freq = [0] * (10**5 + 5)
for i in l: freq[i] -= -1
count = 0
for i in range(10**5 + 5):
    if freq[i] >= 2:
        temp = (freq[i] * (freq[i] - 1)) // 2
        count += temp
for i in l:
    if freq[i] == 1: print(count)
    else:
        temp = freq[i] - 1
        if temp == 1: print(count - 1)
        else:
            yoyo = ((freq[i] * (freq[i] - 1)) // 2) - ((temp * (temp - 1)) // 2)
            print(count - yoyo)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input.split()))
L = [0 for i in range(N)]

total = 0

for i in range(N):
  r = 0
  for j in range(N):
    if i != j and A[i] == A[j]:
      r += 1
  L[i] = r
  total += r

total = total // 2

for i in L:
  print(total - L[i])

Submission status: Runtime Error

Solution code:

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

ct = collections.Counter(A)

ret = []
total = 0
for k,count in ct.items():
    if count > 1:
        total += count * (count-1) // 2

for i,v in enumerate(A):
    if ct[v] > 1:
        count = ct[v]
        adjust = (count-1) * (count-2) // 2 - (count-1) * count // 2
        val = str(total + adjust)
    else:
        val = '0'
    print(val)

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r-1) + cmb(n-1,r)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(n+1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(n+1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()));
lis = [0]*N
ans = [0]*N
ans_selected = [0]*N
ans_sum = 0

for i in A:
    lis[i] += 1

for num, i in enumerate(lis):
    ans[num] = i * (i-1) // 2
    ans_sum += i * (i-1) // 2
    if i != 0:
        ans_selected[num] = (i-1) * (i-2) // 2

for i in A:
    print(ans_sum - ans[i] + ans_selected[i])

Submission status: Runtime Error

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

from collections import Counter

c = Counter(a)

from scipy.special import comb

s = set(c.values())

dic = {}
for ss in s:
    if ss not in dic.keys():
        dic[ss] = comb(ss, 2)
for ss in s:
    ss -= 1
    if ss not in dic.keys():
        dic[ss] = comb(ss, 2)

base = 0
for k in c.keys():
    base += dic[c[k]]

for k in range(len(a)):
    print(int(base - dic[c[a[k]]] + dic[c[a[k]] - 1]))