Problem:


Score : 700 points

Problem Statement

Limak can repeatedly remove one of the first two characters of a string,
    for example abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.

You are given N different strings S_1, S_2, \ldots, S_N.
Among N \cdot (N-1) / 2 pairs (S_i, S_j),
    in how many pairs could Limak obtain one string from the other?

Constraints

2 \leq N \leq 200\,000

S_i consists of lowercase English letters a-z.

S_i \neq S_j

1 \leq |S_i|

|S_1| + |S_2| + \ldots + |S_N| \leq 10^6

Input

Input is given from Standard Input in the following format.

N
S_1
S_2
\vdots
S_N

Output

Print the number of unordered pairs (S_i, S_j)
    where i \neq j and Limak can obtain one string from the other.

Sample Input 1

3
abcxyx
cyx
abc

Sample Output 1

1

The only good pair is (abcxyx, cyx).

Sample Input 2

6
b
a
abc
c
d
ab

Sample Output 2

5

There are five good pairs: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).



Sample input:
3
abcxyx
cyx
abc


Sample output:
1

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
d={}
for i in range(n):
    brr=[0 for j in range(26)]
    x=raw_input()
    y=x[:len(x)-1]
    a.append(x[::-1])
    d[y]=d.get(y,brr)
    d[y][ord(x[-1])-97]+=1
c=0
for i in range(n):
    brr=[0 for j in range(26)]
    x=a[i]
    if(len(x)==1):
        c-=1
    e=""
    d1={}
    for i in x:
        d1[i]=1
    for i in range(len(x)):
        arr=d.get(e,brr)
        for j in range(26):
            if(d1.get(chr(97+j),0)>0):
                c+=arr[j]
                
        d1[x[i]]-=1
        e+=x[i]
print c

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
for i in range(n):
    x=raw_input()
    a.append([len(x),x[::-1]])
a.sort()
d={}
c=0
for i in range(n):
    brr=[0 for j in range(26)]
    x=a[i][1]
    y=x[:len(x)-1]
    e=""
    d1={}
    for i in x:
        d1[i]=d1.get(i,0)+1
    for i in range(len(x)):
        arr=d.get(e,brr)
        for j in range(26):
            if(d1.get(chr(97+j),0)>0):
                c+=arr[j]
        d1[x[i]]-=1
        e+=x[i]
    d[y]=d.get(y,brr)
    d[y][ord(x[0])-97]+=1
print c

Submission status: Wrong Answer

Solution code:
import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 100
#M = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(M,M))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            #self.clue = defaultdict(int)
            self.clue = [0]*26
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

route = []

st = [tt.root]
while st:
    node = st.pop()
    route.append(node)
    st.extend(node.ch.values())

f = lambda c : ord(c)-97
for node in route[::-1]:
    for c,nnode in node.ch.items():
        nnode.clue[f(c)] = nnode.cnt
        for i,v in enumerate(nnode.clue):
            node.clue[i] += v

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[f(last)] - 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1,40))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.clue = {c:0 for c in string.ascii_lowercase}
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

route = []

st = [tt.root]
while st:
    node = st.pop()
    route.append(node)
    st.extend(node.ch.values())

for node in route[::-1]:
    for c,nnode in node.ch.items():
        for k,v in nnode.clue.items():
            node.clue[k] += v
        if nnode.clue[c] == 0:
            node.clue[c] += nnode.cnt

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[last] - 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1,20))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.clue = {c:0 for c in string.ascii_lowercase}
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()
        self.route = [self.root]

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            if w not in node.ch:
                self.route.append(node.ch[w])
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

for node in tt.route[::-1]:
    for c,nnode in node.ch.items():
        for k,v in nnode.clue.items():
            node.clue[k] += v
        if nnode.clue[c] == 0:
            node.clue[c] += nnode.cnt

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[last] - 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1,20))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
T = sorted(T,reverse=True)
ans = 0
for word in T:
    tt.register(word)
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    df = [node]
    while df:
        node = df.pop()
        for c, nnode in node.ch.items():
            if c == last:
                ans += node.ch[last].cnt
            else:
                df.append(nnode)
    ans -= 1
    
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}

ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i :break
    ST[w[i]].update(j,1)
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}

ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i :break
    ST[w[i]].update(j,1)
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    exit()
    ans += ST[q].get(l,r+1)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}

ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i :break
    ST[w[i]].update(j,1)
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    exit()
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r+1)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}

ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i :break
    ST[w[i]].update(j,1)
  exit()
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r+1)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))
"""
class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}

ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i :break
    ST[w[i]].update(j,1)
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r+1)-1
    shori += 1
    if shori == N: break
      
print(ans)
"""

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
words = SLs(N)

nodes = ["#"]
nodes_info = [DD(int)]
chokugo = DD(lambda:DD(int))
tuka = DD(int)
N_nodes = 0

graph = DD(list)

for w in words:
  now = 0
  for i in range(len(w)):
    l = w[len(w)-1-i]
    if not nodes_info[now][l]:
      nodes.append(l)
      N_nodes += 1
      graph[now].append(N_nodes)
      nodes_info.append(DD(int))
      nodes_info[now][l] = N_nodes
    if i == len(w)-1:
      chokugo[now][l] += 1
    now = nodes_info[now][l]
    tuka[now] += 1

N_nodes += 1    

shori = []
def bfs(graph, start):
  N = N_nodes
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    shori.append(u)
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)

bfs(graph,0)

graph2 = [[] for i in range(N_nodes)]
for x in range(N_nodes):
  for y in graph[x]:
    graph2[y].append(x)

size = [DD(int) for i in range(N_nodes)]
for x in shori[::-1]:
  l = nodes[x]
  for y in graph2[x]:
    for k in size[x]:
      size[y][k] += size[x][k]
    size[y][l] += tuka[x]

ans = 0
for i in range(N_nodes):
  for k in size[i]:
    ans += size[i][k] * chokugo[i][k]

print(ans-N)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        cnt[s[1:]] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),1,-1):
            if i == len(s):
                d = ''
            else:
                d = s[i:]
            #ans += bin(cnt[d] & a[i-1]).count('1')

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[]
for i in range(n):
	s.append(input())
	s[i]=s[i][::-1]
s.sort()


count=0
for i in range(n-1):
	j=i+1
	while(True):
		if j>=n or s[i][:-1]!=s[j][:len(s[i])-1]:
			break
		for k in range(len(s[i])-1,len(s[j])):
			if s[i][-1]==s[j][k]:
				count+=1
				break
		j+=1

print(count)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                b = 1
                ##for j in range(26):
                    ##if a[i-1] & b:
                cnt[d%MOD] += 1
                    ##b <<= 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                b = 1
                for j in range(26):
                    if a[i-1] & b:
                        cnt[(d+j+1)%MOD] += 1
                        b <<= 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 31 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                for j in range(26):
                    if a[i-1] & (1<<j) and i < 0:
                        cnt[(d+j+1)%MOD] += 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 31 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 31 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
        C.append(c)

    print(ans)
if __name__ == '__main__':
    main()