Dasha and Nightmares (Codeforces 1800F)
Tags: Others, meet-in-the-middle

Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought $$$n$$$ words consisting of small latin letters $$$s_1, s_2, \ldots, s_n$$$ to the lyceum. Since that day, Dasha has been tormented by nightmares.Consider some pair of integers $$$\langle i, j \rangle$$$ ($$$1 \le i \le j \le n$$$). A nightmare is a string for which it is true:  It is obtained by concatenation $$$s_{i}s_{j}$$$;  Its length is odd;  The number of different letters in it is exactly $$$25$$$;  The number of occurrences of each letter that is in the word is odd. For example, if $$$s_i=$$$ "abcdefg" and $$$s_j=$$$ "ijklmnopqrstuvwxyz", the pair $$$\langle i, j \rangle$$$ creates a nightmare.Dasha will stop having nightmares if she counts their number. There are too many nightmares, so Dasha needs your help. Count the number of different nightmares.Nightmares are called different if the corresponding pairs $$$\langle i, j \rangle$$$ are different. The pairs $$$\langle i_1, j_1 \rangle$$$ and $$$\langle i_2, j_2 \rangle$$$ are called different if $$$i_1 \neq i_2$$$ or $$$j_1 \neq j_2$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of words.The following $$$n$$$ lines contain the words $$$s_1, s_2, \ldots, s_n$$$, consisting of small latin letters.It is guaranteed that the total length of words does not exceed $$$5 \cdot 10^6$$$.

Output: Print a single integer — the number of different nightmares.

Note: In the first test, nightmares are created by pairs $$$\langle 1, 3 \rangle$$$, $$$\langle 2, 5 \rangle$$$, $$$\langle 3, 4 \rangle$$$, $$$\langle 6, 7 \rangle$$$, $$$\langle 9, 10 \rangle$$$.

Sample Inputs:
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz

Sample Outputs:
5

Solution (Python):
import array
import random
import string
import time
from collections import Counter, defaultdict
s = string.ascii_lowercase
M = []
for i in range(26):
    M.append(2 ** i)
A = ord('a')

def solve(lst):
    t = time.time()
    hashes = {}
    targets = []
    hashwords = {}
    for elem in lst:
        hash = 0
        wd = [0] * 26
        for letter in elem:
            idx = ord(letter) - A
            wd[idx] += 1
        for i in range(26):
            if wd[i] % 2 == 1:
                hash += M[i]
        hashes[hash] = hashes.get(hash, 0) + 1
        if not hash in hashwords:
            hashwords[hash] = [0] * 26
        hw = hashwords[hash]
        for i in range(26):
            if wd[i]:
                hw[i] += 1
    res = 0
    for lidx in range(26):
        mask = 2 ** len(s) - 1 - 2 ** lidx
        for (hash, val) in hashes.items():
            shash = mask ^ hash
            if shash in hashes:
                res += (hashes.get(shash, 0) - hashwords.get(shash)[lidx]) * (val - hashwords.get(hash)[lidx])
    return res // 2
t = int(input())
lst = []
for i in range(t):
    lst.append(input())
w = 0
w = solve(lst)
print(w)

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def debug(func):

    def wrapper(*args, **kwargs):
        res = func(*args, **kwargs)
        print('----------------')
        return res
    return wrapper

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

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

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from collections import Counter, defaultdict, deque
MOD = int(1000000000.0 + 7)
M9D = int(998244353)
INF = int(1e+20)

def solve():
    n = II()
    d = defaultdict(lambda : [0] * 26)
    for _ in range(n):
        (s, t) = (0, 0)
        for c in I():
            c = ord(c) - ord('a')
            s ^= 1 << c
            t |= 1 << c
        for i in range(26):
            if t >> i & 1:
                continue
            d[s][i] += 1
    res = 0
    mask = (1 << 26) - 1
    for s in d:
        for i in range(26):
            t = s ^ mask ^ 1 << i
            if t not in d:
                continue
            res += d[s][i] * d[t][i]
    print(res // 2)
    return
solve()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = [input().strip() for _ in range(N)]
So = defaultdict(lambda : defaultdict(int))
Se = defaultdict(lambda : defaultdict(int))
for s in S:
    cnt = [0] * 26
    for i in s:
        i = ord(i) - ord('a')
        cnt[i] += 1
    y = 0
    for c in cnt:
        y <<= 1
        if c:
            y += 1
    x = 0
    for c in cnt:
        x <<= 1
        x += c & 1
    if len(s) % 2 == 0:
        Se[x][y] += 1
    else:
        So[x][y] += 1
ans = 0
msk = (1 << 26) - 1
for (s, n) in So.items():
    t = s ^ msk
    x = t
    for i in range(26):
        bit = 1 << i
        if x & bit:
            nxt = bit ^ x
            if nxt in Se:
                for (a, b) in n.items():
                    for (c, d) in Se[nxt].items():
                        if a | c != msk:
                            ans += b * d
print(ans)