Problem:


Score : 300 points

Problem Statement

We will call a string obtained by arranging the characters contained in a string a in some order, an anagram of a.

For example, greenbin is an anagram of beginner. As seen here, when the same character occurs multiple times, that character must be used that number of times.

Given are N strings s_1, s_2, \ldots, s_N. Each of these strings has a length of 10 and consists of lowercase English characters. Additionally, all of these strings are distinct. Find the number of pairs of integers i, j (1 \leq i < j \leq N) such that s_i is an anagram of s_j.

Constraints

2 \leq N \leq 10^5

s_i is a string of length 10.

Each character in s_i is a lowercase English letter.

s_1, s_2, \ldots, s_N are all distinct.

Input

Input is given from Standard Input in the following format:

N
s_1
s_2
:
s_N

Output

Print the number of pairs of integers i, j (1 \leq i < j \leq N) such that s_i is an anagram of s_j.

Sample Input 1

3
acornistnt
peanutbomb
constraint

Sample Output 1

1

s_1 = acornistnt is an anagram of s_3 = constraint. There are no other pairs i, j such that s_i is an anagram of s_j, so the answer is 1.

Sample Input 2

2
oneplustwo
ninemodsix

Sample Output 2

0

If there is no pair i, j such that s_i is an anagram of s_j, print 0.

Sample Input 3

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa

Sample Output 3

4

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.



Sample input:
3
acornistnt
peanutbomb
constraint


Sample output:
1

Submission status: Runtime Error

Solution code:
# from itertools import product, permutations,combinations
from math import factorial

n = int(input())

# c_hash = {}
c_list = []
# n = 3
for i in range(n):
    s = input()
    c_list.append(''.join(sorted(s)))

# print(sorted(c_list))

c_hash = {}
for c in c_list:
    if c not in c_hash:
        c_hash[c] = 0
    c_hash[c] += 1
count = 0    
for k, v in c_hash.items():
    if v >= 2:

        
        temp = factorial(v) / factorial(2) / factorial(v - 2)
        # temp = len(list(combinations(range(v),2)))
        count += temp

print(round(count))

Submission status: Runtime Error

Solution code:
from scipy.special import comb

n = int(input())
S = [input() for _ in range(n)]
S_sorted = ["".join(sorted(s)) for s in S]
S_sorted = sorted(S_sorted)

ans = 0
cnt = 1
for i in range(1, len(S_sorted)):
    if S_sorted[i] == S_sorted[i-1]:
        cnt += 1
    else:
        ans += comb(cnt, 2, exact=True)
        cnt = 1

if cnt > 1:
    ans += comb(cnt, 2, exact=True)

print(ans)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
h = {}
for _ in range(n):
    s = ''.join(sorted(list(input().strip())))
    if h.get(s) is None:
        h[s] = 1
    else:
        h[s] += 1


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


count = 0
for k, v in h.items():
    count += combinations_count(v, 2)

print(count)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
words = ["".join(sorted(input())) for _ in range(N)]

c = collections.Counter(words)
nums = list(c.values())

nCr = {}
def cmb(n, r):
    if n == 1:
      return 0
    if r == 0 or r == n: 
      return 1
    if r == 1: 
      return n
    if (n,r) in nCr: 
      return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

print(sum([cmb(i,2) for i in nums]))

Submission status: Runtime Error

Solution code:
from array import array

N = int(input())

S = []

for i in range(N):
    s = input()
    slist = list(s)
    slist.sort()
    s = ''.join(slist)
    S.append(s)

FAC = array('l', [0]*(N+1))
FAC[1] = 1

for i in range(2,N+1):
    FAC[i] = FAC[i-1]*i
    
count = 0


for s in set(S):
    s_counts  = S.count(s)
    if s_counts > 1:
        #fac = math.factorial(s_counts)
        #count += fac//2
        count += FAC[s_counts]//2

print(count)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
from math import factorial
def main():
    input = sys.stdin.readline
    N = int(input())
    S = ["".join(sorted(list(input()))).strip() for _ in range(N)]
    #print(S)
    c = Counter(S)
    mosc = c.most_common()
    
    ans = 0
    for i in range(len(mosc)):
        elem = mosc[i]
        if elem[1] > 1:
          n = elem[1]
          r = 2
          ans += factorial(n) / factorial(r) / factorial(n - r)
    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#if 0
date +%Y.%m.%d

题解先咕着。
#endif
#include <cstdio>
#include <algorithm>
#include <map>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef unsigned long long Hash;
inline int input() { int x; scanf("%d", &x); return x; }

const int maxn = 100005;
char s[maxn][15];
std::map<Hash, int> tot;

int main() {
	int n = input(), ans = 0;
	for(int i = 1; i <= n; i ++) {
		scanf("%s", s[i] + 1);
		std::sort(s[i] + 1, s[i] + 11);
		Hash now = 1;
		for(int j = 1; j <= 10; j ++)
			now = now * 27 + s[i][j] - 'a';
		ans += tot[now];
		tot[now] ++;
	}
	printf("%d\n", ans);
}

Submission status: Runtime Error

Solution code:
import math
N = int(input())
ll = []

for i in range(N):
    l = list(input())
    l.sort()
    s = ''.join(l)
    ll.append(s)
ll.sort()
k = 0
ans = 0
for j in range(N-1):
    if ll[j]==ll[j+1]:
        k += 1
    elif k>0:
        ans += math.factorial(k+1)/math.factorial(2)/math.factorial(k+1-2)
        k = 0
if k>0:
    ans += math.factorial(k+1)/math.factorial(2)/math.factorial(k+1-2)
print(int(ans))

Submission status: Runtime Error

Solution code:
import collections
from scipy.special import comb
N = int(input())
S = [input() for i in range(N)]
# print(S)
S_new = []
for s in S:
    S_new.append(''.join(sorted(s)))
# print(S_new)
c = collections.Counter(S_new)
# print(c)
cnt = 0
for num in c.values():
    if num > 1:
        if num == 2:
            cnt += 1
        else:
            cnt += comb(num, 2, exact=True)# a = comb(n, r)
print(cnt)

Submission status: Runtime Error

Solution code:
# ABC 137, c
from collections import Counter
import math
n = int(input())
d = []
for i in range(n):
    s = ''.join(sorted(input()))
    d.append(s)

C = Counter(d).most_common()
def comb(n, r):
    if n < r:
        return(0)
    f = math.factorial
    return (f(n) / f(r) / f(n-r))

count = 0
for key, value in C:
    count += comb(value, 2)
print(int(count))

Submission status: Runtime Error

Solution code:
n= int(input())
s = [[*input()] for _ in range(n)]

for i in range(n):
	s[i].sort()

ans = 0
# print(s)
for i in range(n-1):
	for j in range(i+1,n):
		if s[i] == s[j]:
			ans +=1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
ls = []
for i in range(n):
    ls.append(input())
l=[[0 for j in range(26)] for i in range(n)]
for i in range(n):
    for s in ls[i]:
        alpha = ord(s) - ord("a") + 1
        l[i][alpha] +=1
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if l[i] == l[j]:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = [input() for _ in range(N)]

Dic = [1]*N
prime = {"a":2,"b": 3, "c":5, "d":7,"e": 11,"f": 13,"g": 17,"h": 19,"i": 23,"j": 29,"k": 31,"l": 37,"m": 41, "n":43,"o": 47,"p": 53,"q": 59,"r": 61,"s": 67,"t": 71,"u": 73,"v": 79,"w": 83,"x": 89,"y": 97,"z":101}

from math import factorial

def comb(n,r):
    if n - r>= 0:
        return factorial(n) / factorial(r)*factorial(n - r)
    else:
        return 0


for i in range(N):
    for s in S[i]:
        Dic[i]*= prime[s]
Dic.sort()
pre = Dic[0]
ans = 0
temp = 1
for d in Dic[1:]:
    if pre == d:
        temp += 1
    else:
        ans += comb(temp,2)
        pre = d
        temp = 1
ans += comb(temp,2)
print(int(ans))

Submission status: Runtime Error

Solution code:
n = int(input())
l = [input() for i in range(n)]

from collections import Counter
ans = 0
for w1,w2 in l:
  if Counter(w1) == Counter(w2):
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from scipy import special
n=int(input())
s=[''.join(sorted(input())) for _ in range(n)]
s=sorted(s)
ans=0
c=1
t=s[0]
for i in range(1,n):
    if t==s[i]:
        c+=1
    else:
        ans+=special.comb(c,2,True)
        t=s[i]
        c=1
ans+=special.comb(c,2,True)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = []
for _ in range(N):
    s = [0]*26
    for i in map(lambda: ord(c)-97, input()):
        s[i] += 1

res = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            res += 1

print(res)

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    string_type = {}
    for s in inputs:
        count = {}
        s_list = list(s)
        s_list.sort()
        for c in s_list:
            if c in count:
                count[c] += 1
            else:
                count[c] = 1
        key = ""
        for k in count.keys():
            key += "{}{}".format(k, count[k])
        if key in string_type:
            string_type[key] += 1
        else:
            string_type[key] = 1

    comb_count = 0
    for v in string_type.values():
        if v != 1:
            if v == 2:
                comb_count += 1
            else:
                comb_count += factorial(v) / factorial(2) / factorial(v-2)
    return int(comb_count)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N))
    print(ret)

Submission status: Runtime Error

Solution code:
import collections
from math import factorial

N =int(input())
cnts = [frozenset(collections.Counter(list(input())).items()) for _ in range(N)]
xs = collections.Counter(cnts)
ans = 0
for _,v in xs.items():
    if v>=1:
        a = factorial(v) // (2*factorial(v - 2))
        ans +=a
print(ans)

Submission status: Runtime Error

Solution code:

  File "./main.py", line 16, in solve
    result += int((v-1) * 0.5 (1 + v-1))
TypeError: 'float' object is not callable

Submission status: Runtime Error

Solution code:
import collections
from math import factorial
n = int(input())
s = [''.join(sorted(input())) for i in range(n)]
c = collections.Counter(s)
count = list(c.values())
ans = 0
for num in count:
    if num >= 2:
        b = factorial(num) / factorial(2) / factorial(num - 2)
        ans += int(b)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())

string_dict = defaultdict(int)

for i in range(N):
    inp = list(input())
    inp.sort()

    string_dict["".join(inp)] += 1
# print(string_dict)


def kaijo(N):
    if N == 0:
        return 0
    if N == 1:
        return 0
    return N-1 + kaijo(N-1)


count = 0
for i in string_dict.values():
    if i >= 2:
        # print(kaijo(i))
        count += kaijo(i)
print(count)

Submission status: Runtime Error

Solution code:

nCr = {}


def cmb(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n, r) in nCr:
        return nCr[(n, r)]
    nCr[(n, r)] = cmb(n-1, r) + cmb(n-1, r-1)
    nCr[(n, r)] = nCr[(n, r)]
    return nCr[(n, r)]


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


N = int(input())
dct = {}

for i in range(N):
    tmp = input()
    #print("head   ",tmp)
    tmp = "".join(sorted(tmp))
    try:
        dct[tmp] += 1
    except:

        dct[tmp] = 1


res = 0
for sdct in dct:
    if dct[sdct] > 1:
        res += cmb(dct[sdct], 2)

print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
from scipy.special import comb

def solve(N: int, s: "List[str]"):
    print(sum([comb(v, 2, exact=True) for v in Counter(s).values()]))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ ' '.join(sorted(next(tokens))) for _ in range(N) ]  # type: "List[str]"
    solve(N, sorted(s))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
from scipy.special import comb
N =int(input())
cnts = [frozenset(collections.Counter(list(input())).items()) for _ in range(N)]
xs = collections.Counter(cnts)
ans = 0
for _,v in xs.items():
    if v>=1:
        a = comb(v, 2, exact=True)
        ans +=a
print(ans)

Submission status: Runtime Error

Solution code:
import collections
import sys
sys.setrecursionlimit(100000000)

from math import factorial
def ncr(n,r):
 if n>2:
  return factorial(n) / factorial(r) / factorial(n - r)
 else:
  return 1
def solve():
  n = int(input())
  query = []
  for i in range(n):
    a = sorted(input())
    query.append("".join(a))

  c = collections.Counter(query)
  ans = 0
  tmp = c.values()

  for i in tmp:
    if i >=2:
      ans += ncr(i,2)
  print(int(ans))
  
solve()

Submission status: Runtime Error

Solution code:
N = int(input())
a = [sorted(list(int(input()))) for i in range(N)]
b = 0
for i in a:
 b = b + a.count(i)
print(b / 2)

Submission status: Runtime Error

Solution code:
import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

from math import factorial

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    #mng = [][]
    sl = []
    mng = []
    for _ in range(N):
        s = set(sys.stdin.readline().rstrip())
        if s in sl:
            i = sl.index(s)
            mng[i] += 1
        else:
            sl.append(s)
            mng.append(0)

    ans = 0
    r = 2
    #print(mng)
    for n in mng:
        if n > 0:
            n += 1
            ans += factorial(n) / factorial(r) / factorial(n - r)

    print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter as cl
N = int(input())
List=[input() for i in range(5)]

count = 0
for x in range(N):
	for y in range(x+1,N):
      if cl(List[x]) == cl(List[y]):
        count+=1

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
from scipy.special import comb

def solve(N: int, s: "List[str]"):
    print(sum([comb(v, 2, exact=True) for v in Counter(s).itervalues()]))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ ' '.join(sorted(next(tokens))) for _ in range(N) ]  # type: "List[str]"
    solve(N, sorted(s))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import factorial
n = int(input())
ct_ls = []
for i in range(n):
    ct_ls.append("".join(sorted(input())))
ct = Counter(ct_ls)
_ct = 0
for n in ct.values():
    if n >= 2:
        _ct += factorial(n) / factorial(2) / factorial(n - 2)
print(int(_ct))

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
N = 10**4
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )

def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()
a =[]

for i in range(n):
    k = list(input())
    k.sort()
    a.append(k)

a.sort()
b = s(a)

co = 0

for i in range(len(b)):
    if b[i][1] != 1:
        co += cmb(b[i][1],2)
print(co)

Submission status: Runtime Error

Solution code:
3
acornistnt
peanutbomb
constraint

Submission status: Runtime Error

Solution code:
import collections

from math import factorial
def ncr(n,r):
 if n>2:
  return factorial(n) / factorial(r) / factorial(n - r)
 else:
  return 1
def solve():
  n = int(input())
  query = []
  for i in range(n):
    a = sorted(input())
    query.append("".join(a))

  c = collections.Counter(query)
  ans = 0
  tmp = c.values()
  for i in tmp:
    if i >=2:
      ans += ncr(i,2)
  print(int(ans))
solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
acc = [0] * 11
for i in range(10):
    acc[i + 1] = acc[i] + (i + 1)
n = int(input())
s = [input() for _ in range(n)]
dic = {}
for i in range(n):
    srt = ''.join(sorted(s[i]))
    dic[srt] = dic[srt] + 1 if srt in dic else 1
ans = 0
for v in dic.values():
    ans += acc[v - 1]
print(ans)

Submission status: Runtime Error

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

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


def main():
    n=int(input())
    l=[cmb(i,2) for i in Counter(["".join(sorted(input()))for i in range(n)]).values()]
    print(sum(l))
                    
        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    a,b=map(int,input().split())
    print(max(a*b,a-b,a*b))
                    
        
if __name__ == '__main__':
    main()