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: Accepted

Solution code:
from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}
flags = [1 << (i * 18) for i in range(26)]

trie_chr = [-1]
trie_children = [{}]
trie_counter = [0]
trie_fin = [0]
s_fin_node = []
l = 1

for s in sss:
    node = 0
    trie_counter[node] += 1
    for i in range(len(s) - 1, 0, -1):
        c = ord(s[i]) - 97
        if c in trie_children[node]:
            node = trie_children[node][c]
            trie_counter[node] += 1
        else:
            trie_chr.append(c)
            trie_children.append({})
            trie_fin.append(0)
            trie_children[node][c] = l
            trie_counter.append(1)
            node = l
            l += 1
    trie_fin[node] += 1
    s_fin_node.append(node)

trie_flags = [0] * l

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        flag |= flags[ord(c) - 97]
    node = 0
    if len(s) > 1 and trie_fin[node] > 0:
        trie_flags[node] += flag

    for i in range(len(s) - 1, 1, -1):
        c = s[i]
        k = ord(c) - 97
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= flags[k]

        node = trie_children[node][k]
        # print(s, i, node, trie_counter[node])
        if trie_counter[node] == 1:
            break
        if trie_fin[node] > 0:
            trie_flags[node] += flag
            # print('add', s, i)

# print([chr(c) if c >= 0 else -1 for c in trie_chr])
# print(trie_counter)
# print(trie_fin)
# print(trie_flags)
# print(s_fin_node)

ans = 0
mask = (1 << 18) - 1
for i, s in enumerate(sss):
    cnt = (trie_flags[s_fin_node[i]] >> ((ord(s[0]) - 97) * 18)) & mask
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:

class TN(object):
	def __init__(self):
		self.h = {}
		self.count = 0
		self.need = collections.Counter()


ais = [raw_input() for _ in range(int(raw_input()))]
ais.sort(key = len)
import collections
cc = collections.Counter()

ans = 0
root = TN()
for w in ais:
	
	###COUNT
	cur =  root
	for j in range(len(w)-1, -1, -1):
		for k in cur.need:
			if k in w[:j+1]:
				ans += cur.need[k]
		if w[j] in cur.h:
			cur = cur.h[w[j]]
		else:
			break
	###UPDATE
	cur = root
	for j in range(len(w) - 1, 0, -1):
		if w[j] not in cur.h:
			cur.h[w[j]] = TN()
		cur = cur.h[w[j]]
	cur.need[w[0]] += 1

print ans

Submission status: Accepted

Solution code:
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        dic_last = {}
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
                    hh = H1[i] * (mod2+1) + H2[i]
                    if hh not in dic_last:
                        dic_last[hh] = [0] * 26
                    for j in range(26):
                        if cnt[i][j] > 0:
                            dic_last[hh][j] += 1
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 * (mod2+1) + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                if h in dic_last:
                    ans += dic_last[h][last]
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math, time
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIF(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n = II()
    s = [None] * n
    dp = [None] * n
    for i in range(n):
        dp[i] = [-1] * 26
        s[i] = [input().rstrip()[::-1], i]
    for i in range(n):
        si,_ = s[i]
        dpi = dp[i]
        for j in range(len(si)):
            x = ord(si[j]) - ord("a")
            dpi[x] = j
    d = [s]
    ans = 0
    for i in range(10 ** 6):
        nd = []
        if not d: break
        for lis in d:
            tmp = [[] for i in range(26)]
            for l, k in lis:
                p = ord(l[i]) - ord("a")
                if len(l) == i + 1:
                    for x, m in lis:
                        if k != m:
                            if dp[m][p] >= i:
                                ans += 1
                else:
                    tmp[p].append((l, k))
            for k in tmp:
                if k:
                    nd.append(k)
        d = nd
    print(ans)
    return
#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

ans = 0
def scomp(S):
    L = 1+max(S)
    table = [0]*L
    for s in S:
        table[s] += 1
    it = [None]*L
    cnt = 0
    for i in range(L):
        it[i] = cnt
        if table[i]:
            cnt += 1
    return it

import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
        self.count = [0]*sigma
        self.par = None
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
                vn[cs].par = vn
            vn = vn[cs]
        vn.end = True
    
    def up(self, S):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]

        k = [0]*self.sigma
        ls = len(S)
        for i in range(ls-1, -1, -1):
            vn = vn.par
            s = S[i]
            k[s] = 1
            for i in range(self.sigma):
                vn.count[i] += k[i]
    
    def count(self, S, ss):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
        
        global ans
        ans += vn.count[ss]

ans = 0



N = int(readline())
A = [list(map(lambda x: ord(x)-97, readline().strip()))[::-1] for _ in range(N)]

T = Trie(26)

for a in A:
    T.add(a)
for a in A:
    T.up(a)
for a in A:
    s = a[:-1]
    t = a[-1]
    T.count(s, t)

print(ans-N)

Submission status: Accepted

Solution code:
from collections import defaultdict
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

N = int(input())
Slist = []
for i in range(N):
    S = input()
    Slist.append(S)
Slist.sort(key=len)
dic = defaultdict(lambda:defaultdict(int))
ans = 0
for S in Slist:
    alp = set()
    l = len(S)
    RH = RollingHash(S,37,10**18+9)
    for i in range(len(S)):
        alp.add(S[i])
        alpdic = dic[RH.get(i+1,l)]
        for X in alpdic.keys():
            if X in alp:
                ans += alpdic[X]
    dic[RH.get(1,l)][S[0]] += 1
print(ans)

Submission status: Accepted

Solution code:

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y



def solve(L):
    L = [tuple(ord(c)-ord('a') for c in reversed(s)) for s in L]
    trie = ([None]*26, [])

    for s in L:
        node = trie
        for c in s[:-1]:
            leaf,_ = node
            if leaf[c] is None:
                leaf[c] = ([None]*26, [])
            node = leaf[c]
        node[1].append(s[-1])
    
    cnt = 0
    for s in L:

        app = [0]*26
        for c in s:
            app[c] += 1

        node = trie
        for c in s:
            if node is None:
                break
            leaf,tail = node
            for d in tail:
                if app[d] > 0:
                    cnt += 1
            app[c] -= 1
            node = leaf[c]
    return cnt - len(L)




if __name__ == '__main__':
    N = int(readline())
    L = [s.decode().rstrip() for s in read().split()]
    print(solve(L))

Submission status: Runtime Error

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
    exit()
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Runtime Error

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

Solution code:
N = int(input())
A = []
for _ in range(N):
    A.append(str(input()))

def work(a, b):
    position = b[0:2].find(a)
    tmp = b[2:]
    if (position >= 0):
        tmp1 = b[0] if (position == 1) else b[1]
        return tmp1 + tmp
    else :
        return None

count = 0
for i in A:
    ri = i[::-1]
    for v in A:
        if (i == v or len(i) > len(v)):
            continue
 
        result = v[::-1]
        for index, value in enumerate(list(ri)):
            result = work(value, result)
            if result:
                if (len(list(ri)) == index + 1):
                    count += 1
            else:
                break

print(count)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool sortbylen(string a, string b)
{
	return a.length() < b.length();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s;
    s.resize(n);

    for (int i = 0; i < n; i++)
		cin >> s[i];

    sort(s.begin(), s.end(), sortbylen);

    int c = 0;
    for (int i = 0; i < n; i++)
	{
        for (int j = i + 1; j < n; j++)
        {
			int x, y;
			x = s[i].length() - 1;
			y = s[j].length() - 1;
			while (x >= 0)
			{
				if (y >= 0 && (s[i][x] == s[j][y])
					|| y > 0 && (s[i][x] == s[j][--y]))
					--x, --y;
				else
					goto next;
			}
			c++;
			next: ;
		}    
	}
    cout << c;

    return 0;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool sortbylen(string a, string b)
{
	return a.length() < b.length();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s;
    s.resize(n);

    for (int i = 0; i < n; i++)
		cin >> s[i];

    sort(s.begin(), s.end(), sortbylen);

    int c = 0;
    for (int i = 0; i < n; i++)
	{
        for (int j = i + 1; j < n; j++)
        {
			int x, y;
			x = s[i].length() - 1;
			y = s[j].length() - 1;
			while (x >= 0)
			{
				if (y >= 0 && (s[i][x] == s[j][y])
					|| y > 0 && (s[i][x] == s[j][--y]))
					--x, --y;
				else
					continue;
			}
			c++;
		}    
	}
    cout << c;

    return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())

word = []
for i in range(n):
  input_line = input()
  word.append(input_line)
  #print(word[i])
  
# 一致する可能性のある組み合わせを数える cou1
# 一致する可能性のある組み合わせを格納するリスト case
cou1 = 0
case = []

for i in range(n):
  check1 = word[i]
  for j in range(n):
    if i != j:
      check2 = word[j]
      k = 0
      l = 0
      while k < len(word[i]) and l < len(word[j]):
        if check1[k] == check2[l]:
          k += 1
          l += 1
          if l == len(word[j]):
            case.append([i, j])
            cou1 += 1
            print(case)
            break
        else:
          l += 1
          k = 0
      l = 0
    else:
      continue

print(cou1)
      
#正解の組み合わせを数える cou2
cou2 = 0
for i in range(cou1):
  j = case[i][0]
  k = case[i][1]
  l = len(word[j])
  #m = len(word[k])
  if l == 1:
    cou2 += 1
  elif word[j][1:] == word[k][1:]:
    cou2 += 1
  else:
    continue

#print(cou2)

Submission status: Runtime Error

Solution code:
def C(x):
    s = 0
    t = N
    for i in range(len(x)-1):
        t = upper_bound(x, i, s, t)
        s = lower_bound(x, i, s, t)
    
    res = 0
    for i in range(s, t):
        if x[-1] in S[i][len(x)-1:]:
            res += 1
    
    return res - 1
    

def lower_bound(x, i, s, t):
    s, t = s-1, t
    while t - s > 1:
        m = (s + t) // 2
        if len(S[m]) >= i and S[m][i] >= x[i]:
            t = m
        else:
            s = m
    
    return t

def upper_bound(x, i, s, t):
    s, t = s-1, t
    while t - s > 1:
        m = (s + t) // 2
        if len(S[m]) >= i and S[m][i] > x[i]:
            t = m
        else:
            s = m
    
    return t
    

N = int(input())
S = [tuple(reversed(input())) for _ in range(N)]
S.sort()
ans = 0
for x in S:
    ans += C(x)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(S):
    S = S.copy()
    l_ind = np.where(S == -1)[0][:-1] + 1
    r_ind = np.where(S == -1)[0][1:]

    # 逆順にしておく
    N = len(l_ind)
    for i in range(N):
        S[l_ind[i]:r_ind[i]] = S[l_ind[i]:r_ind[i]][::-1]

    # Trie木の構築
    path = np.zeros_like(S)
    child = np.zeros((len(S), 26), np.int32)
    is_end = np.zeros(len(S), np.bool_)

    n_node = 1
    for i in range(N):
        node = 0
        for j in range(l_ind[i], r_ind[i]):
            path[j] = node
            if child[node][S[j]] == 0:
                child[node][S[j]] = n_node
                n_node += 1
            node = child[node][S[j]]
        is_end[node] = True
    child = child[:n_node]
    is_end = is_end[:n_node]
    ans = 0
    for i in range(N):
        se = 0
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            se |= 1 << S[j]
            node = path[j]
            for k in range(26):
                if se & 1 << k:
                    if is_end[child[node][k]]:
                        ans += 1
    return ans - N

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba import njit, b1, i4, i8, f8
    import numba
    from numba.pycc import CC
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i4[:], ))
    cc.compile()

from my_module import main

N = int(readline())
S = np.array(list(read().rstrip()), np.int32)

S[S == ord('\n')] = -1
S[S > 0] -= ord('a')
S = np.insert(S, 0, -1)
S = np.append(S, -1)

print(main(S))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MASK61 = (1 << 61) - 1

@njit((i8, ), cache=True)
def rh_modulo(x):
    xu, xd = x >> 61, x & MASK61
    x = xu + xd
    if x >= MASK61:
        x -= MASK61
    return x


@njit((i8, i8), cache=True)
def rh_multiply(a, b):
    au, ad = a >> 31, a & MASK31
    bu, bd = b >> 31, b & MASK31
    x = ad * bu + au * bd
    xu, xd = x >> 30, x & MASK30
    return rh_modulo(au * bu * 2 + xu + (xd << 31) + ad * bd)


@njit((i8, i8), cache=True)
def rh_pows(base, max_len):
    pows = np.empty(max_len, np.int64)
    pows[0] = 1
    for n in range(1, max_len):
        pows[n] = rh_multiply(pows[n - 1], base)
    return pows


@njit((i8[:], i8, i8[:]), cache=True)
def compute_rh(pows, base, S):
    N = len(S)
    RH = np.empty(N, np.int64)
    RH[0] = S[0] + 10
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n] + 10
        if x >= MASK61:
            x -= MASK61
        RH[n] = x
    return RH


@njit((i8[:], i8, i8[:], i8, i8), cache=True)
def rh_substr(pows, base, RH, l, r):
    h = RH[r]
    if l > 0:
        h -= rh_multiply(RH[l], pows[r - l])
    if h < 0:
        h += MASK61
    return h

@njit((i8[:], ), cache=True)
def main(S):
    S = S.copy()
    l_ind = np.where(S == -1)[0][:-1] + 1
    r_ind = np.where(S == -1)[0][1:]
    N = len(l_ind)
    # 逆順にしておく
    for i in range(N):
        S[l_ind[i]:r_ind[i]] = S[l_ind[i]:r_ind[i]][::-1]

    # rolling hashの計算
    max_len = len(S) + 10
    base = np.random.randint(0, 1 << 31)
    pows = rh_pows(base, max_len)
    RH = np.zeros_like(S)
    for i in range(N):
        RH[l_ind[i]:r_ind[i]] = compute_rh(pows, base, S[l_ind[i]:r_ind[i]])

    # 後ろ（自身も含む）に置ける文字集合の計算
    sets = np.zeros_like(S)
    for i in range(N):
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            sets[j] = sets[j + 1] | 1 << S[j]

    # 作れる組 (prefix, 右からの1文字)をすべて計算する
    ptr = 0
    nums = np.empty(len(S) * 26 + 10, np.int64)
    for i in range(N):
        for j in range(l_ind[i], r_ind[i]):
            for k in range(26):
                if sets[j] & 1 << k:
                    h = rh_multiply(RH[j - 1], base) + k
                    nums[ptr] = h
                    ptr += 1
    nums = nums[:ptr]
    nums.sort(kind='mergesort')
    # 各文字列とマッチングする対象を数える
    ans = 0
    for i in range(N):
        h = rh_multiply(RH[r_ind[i] - 2], base) + S[r_ind[i] - 1]
        cnt = np.searchsorted(nums, h, 'right')
        cnt -= np.searchsorted(nums, h, 'left')
        ans += cnt - 1  # 自分を除外
    print(ans)

N = int(readline())
S = np.array(list(read().rstrip()), np.int64)

S[S == ord('\n')] = -1
S[S > 0] -= ord('a')
S = np.insert(S, 0, -1)
S = np.append(S, -1)

main(S)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
### ローリングハッシュ rolling hash
import random
M = 10**9+7
b = random.choice(range(M))
l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c:i+1 for i,c in enumerate(l)}
def rhash(s):
    ans = 0
    v = 1
    l = len(s)
    vs = [None]*l
    rs = [None]*l
    tmps = [None]*l
    for i in range(l-1, -1, -1):
        ans += d[s[i]]*v
        vs[i] = v
        v *= b
        ans %= M
        v %= M
        rs[i] = ans
        tmps[i] = s[i:]
    rs.append(0)
    tmps.append("")
    tmp = set()
    ss = set()
#     out = set()
    for i in range(l):
        tmp.add(s[i])
        for c in tmp:
            ss.add((rs[i+1] + vs[i]*d[c])%M)
#             out.add(c+tmps[i+1])
    return ss, ans#, out
dd = defaultdict(list)
ans = 0
rs = [None]*n
for i in range(n):
    ss, rs[i] = rhash(input())
    assert rs[i] in ss
    for item in ss:
        dd[item].append(i)
for i in range(n):
    ans += len(dd[rs[i]])-1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

M = 10**6
child = [[-1] * 26]
is_end = [False] * M

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
paths = [[] for _ in range(N)]
for i, s in enumerate(S):
    node = 0
    for c in s:
        c = ord(c) - ord('a')
        paths[i].append(node)
        if child[node][c] == -1:
            child[node][c] = len(child)
            child[node].append([-1] * 26)
        node = child[node][c]
    is_end[node] = True

ans = 0
for i, s in enumerate(S):
    suffix = set()
    for j in range(len(s) - 1, -1, -1):
        suffix.add(ord(s[j]) - ord('a'))
        node = paths[i][j]
        for c in suffix:
            ans += is_end[child[node][c]]
print(ans - N)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

nums = [float(input()) for _ in range(N)]

two_fives = []


for i, num in enumerate(nums):
    int_converted = int(num * (10**9))
    
    two_div_count = 0
    while int_converted % 2 == 0:
        two_div_count += 1
        int_converted //= 2
    
    five_div_count = 0
    while int_converted % 5 == 0:
        five_div_count += 1
        int_converted //= 5

    two_fives.append((two_div_count,five_div_count))


ok_count = 0

two_five_exists = np.zeros((19,19), dtype=int)

for i in range(N):    
    two_count, five_count = two_fives[i]
    ok_count += two_five_exists[two_count, five_count]
    
    two_pair = 18 - two_count
    five_pair = 18 - five_count    
    two_five_exists[two_pair:, five_pair:] += 1

print(ok_count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

MOD = (1 << 61) - 1
mod_pow = [1] * (10**5 * 5 + 10)
base = 1009

for i in range(10**5 * 5 + 9):
    mod_pow[i+1] = mod_pow[i] * base % MOD

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 2)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * mod_pow[r-l] % self.mod
        return t % self.mod

ss = []
n = int(input())
for _ in range(n):
    ss.append(input().rstrip())
ss.sort(key=lambda x: len(x), reverse=True)

words = dict()
ans = 0
orda = ord("a")
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len-1)
    if rh in words:
        ans += words[rh][ord(s_rev[-1]) - orda]
    initial = set()
    for i, ch in enumerate(s):
        initial.add(ord(ch) - orda)
        for key in initial:
            rh = RH.get(0, word_len-i-1)
            if rh in words:
                words[rh][key] += 1
            else:
                words[rh] = [0] * 26
                words[rh][key] += 1
print(ans)