题意概述

有 $N$ 个长度为 $M$ 的字符串，每个字符串由小写字母和 ? 组成。
? 可以替换为任意小写字母。
问有多少对字符串 $(i,j)$（$i<j$），使得存在一种替换 ? 的方式，使两个字符串完全相同。

---

问题分析

两个字符串能匹配的条件是：对于每个位置 $k$（$1 \le k \le M$），
要么两个字符相同，要么至少有一个是 ?。
即：不存在某个位置 $k$ 使得两个字符都是字母且不同。

设两个字符串为 $s$ 和 $t$，则它们能匹配的充要条件是： [ \forall k,\quad s[k] = t[k] \ \text{或}\ s[k] =\ ? \ \text{或}\ t[k] =\ ? ] 等价地： [ \forall k,\quad (s[k] \neq \ ? \ \text{且}\ t[k] \neq \ ?) \implies s[k] = t[k] ]

---

暴力方法

枚举所有 $N^2$ 对字符串并逐位检查，复杂度 $O(N^2 M)$，$N$ 可达 $5\times 10^4$，不可行。

---

利用 $M$ 很小的特点

$M \le 6$，这提示我们可以用位运算或状态压缩。

考虑对于每个字符串，它在每个位置有三种可能：

1. 是某个字母 $c$（$1 \le c \le 26$）
2. 是 ?

我们可以将 ? 视为“任意字母”，所以匹配条件就是：对于所有位置，要么至少一个是 ?，要么字母相同。

---

转化为集合包含问题

对于一个字符串 $s$，定义两个集合：

• 确定位置集 $A_s$：$s$ 中不是 ? 的位置集合。
• 字母模式 $P_s$：在确定位置上对应的字母序列（可以压缩成一个整数）。

两个字符串 $s$ 和 $t$ 能匹配的条件是：

1. 在它们都有确定字母的位置上，字母必须相同。
2. 换句话说，$A_s \cap A_t$ 中的位置上，$P_s$ 和 $P_t$ 必须一致。

---

等价类划分

我们可以将每个字符串 $s$ 映射为一个“模式”：

• 枚举所有可能的位置子集 $mask$（$0 \le mask < 2^M$），对应 $s$ 中确定字母的位置集合。
• 在该子集上，对应位置的字母构成一个“确定字母串”。

两个字符串匹配当且仅当：

• 它们在某些位置都确定字母，且这些位置的字母相同。
• 即：存在一个非空位置集合 $C = A_s \cap A_t$，使得 $s$ 和 $t$ 在 $C$ 上的字母完全一致。

---

更直接的方法：容斥或哈希

因为 $M$ 很小，可以枚举所有 $2^M$ 个位置子集 $mask$。
对于每个字符串 $s$，我们可以计算它在 $mask$ 指定的位置上的“部分字符串”：

• 如果 $mask$ 中某个位置在 $s$ 中是 ?，则 $s$ 在这个 $mask$ 上没有定义（或者视为特殊标记）。
• 否则，取出这些位置上的字母，构成一个字符串 $sub(s, mask)$。

两个字符串 $s$ 和 $t$ 能匹配的条件是： [ \exists mask,\quad sub(s, mask) = sub(t, mask) \ \text{且} \ mask \subseteq A_s \cap A_t ] 其实等价于：在它们都确定字母的位置上字母相同。

所以我们可以用哈希来统计：
对于每个字符串 $s$，枚举所有子集 $mask \subseteq A_s$，将 $(mask, sub(s, mask))$ 进行哈希，记录出现次数。
但这样每个字符串要枚举 $2^{|A_s|}$ 种子集，最坏 $2^M = 64$ 种，$N=5\times 10^4$，总枚举量约 $3.2\times 10^6$，可以接受。

---

统计配对数量

注意：两个字符串 $s$ 和 $t$ 可能在多个 $mask$ 下都满足 $sub(s, mask) = sub(t, mask)$，这会重复计数。

为了避免重复，我们规定：只取 $mask = A_s \cap A_t$，即它们都确定字母的位置集合。
在这个 $mask$ 上，它们必须字母一致才能匹配。

---

算法步骤

1. 对每个字符串 $s$，确定 $A_s$（哪些位置是字母）。
2. 将 $s$ 在 $A_s$ 上的字母串提取出来（长度 $|A_s|$），并编码成一个整数（26 进制或直接字符串哈希）。
3. 我们定义一个关键表示：$(A_s, code_s)$，其中 $code_s$ 是 $s$ 在 $A_s$ 上的字母编码。
4. 两个字符串 $s$ 和 $t$ 能匹配当且仅当：
   • 令 $mask = A_s \cap A_t$
   • $s$ 和 $t$ 在 $mask$ 上的字母序列相同

等价地，我们可以枚举所有可能的 $mask$（$0 \le mask < 2^M$），然后考虑所有 $A_s$ 包含 $mask$ 的字符串，在 $mask$ 上的字母编码必须相同才能匹配。

---

具体实现：按 $mask$ 分组

对于每个 $mask$，我们只关心那些 $A_s \supseteq mask$ 的字符串（即 $mask$ 中所有位置在 $s$ 中都是字母）。
将这些字符串按照在 $mask$ 上的字母编码分类。
同一类中的任意两个字符串都能匹配吗？
检查：设 $s$ 和 $t$ 在 $mask$ 上字母相同，且 $mask \subseteq A_s$，$mask \subseteq A_t$。
那么对于任意位置 $k$：

• 如果 $k \in mask$，则 $s[k]=t[k]$（字母相同）
• 如果 $k \notin mask$，则 $s[k]$ 或 $t[k]$ 至少有一个是 ?（因为 $mask$ 是它们确定字母的交集，之外的位至少一个是 ?）

所以确实能匹配。

因此，对于每个 $mask$，将 $A_s \supseteq mask$ 的字符串按 $mask$ 上的字母编码分组，同一组内的字符串两两可匹配。

---

避免重复计数

同一个字符串对 $(s,t)$ 可能被多个 $mask$ 统计到。
我们需要保证每个字符串对只被计算一次。

注意到：如果 $s$ 和 $t$ 能匹配，那么它们的所有公共确定字母位置集合 $C = A_s \cap A_t$ 上字母相同。
对于 $mask = C$，它们会被分到同一组。
对于 $mask \subset C$，它们也会被分到同一组。
所以会被多次统计。

要唯一确定，我们应取 $mask = A_s \cap A_t$，即最大公共确定字母集。
如何保证只按这个 $mask$ 统计？

---

利用容斥原理

设 $f[mask]$ 表示在 $mask$ 上字母编码相同的字符串对数（要求 $mask \subseteq A_s$ 且 $mask \subseteq A_t$）。
这个 $f[mask]$ 会重复计数那些在更大 $mask' \supset mask$ 上也相同的对。

设 $g[mask]$ 表示恰好在 $mask$ 上字母编码相同（且不在更大的公共确定字母集上相同）的对数。

那么： [ f[mask] = \sum_{mask' \supseteq mask} g[mask'] ] 由 Möbius 反演（在高维上是容斥）： [ g[mask] = f[mask] - \sum_{mask' \supset mask} g[mask'] ] 我们可以按 $mask$ 从大到小（按位数从多到少）计算 $g[mask]$。

最终答案是： [ ans = \sum_{mask} g[mask] ]

---

计算 $f[mask]$

对于每个 $mask$，收集所有 $A_s \supseteq mask$ 的字符串，将它们按在 $mask$ 上的字母编码分类。
设某类有 $cnt$ 个字符串，则对 $f[mask]$ 的贡献为 $\binom{cnt}{2}$。

---

算法总流程

1. 预处理每个字符串 $s$ 的 $A_s$（确定字母位置集合），以及它在 $A_s$ 上的字母编码 $code_s$（可哈希）。
2. 枚举所有 $mask$（$0 \le mask < 2^M$）：
   • 遍历所有字符串 $s$，如果 $mask \subseteq A_s$，则取出 $s$ 在 $mask$ 上的字母编码 $code(s, mask)$（根据 $mask$ 提取对应位置字母并哈希）。
   • 用哈希表统计每个 $code$ 的出现次数 $cnt$。
   • $f[mask] = \sum \binom{cnt}{2}$。
3. 从大到小枚举 $mask$（按二进制中 1 的个数从多到少）：
   • $g[mask] = f[mask]$
   • 枚举所有 $mask' \supset mask$（可通过枚举超集实现），$g[mask] -= g[mask']$。
4. 答案 $ans = \sum_{mask} g[mask]$。

---

复杂度

$M \le 6$，所以 $2^M \le 64$。
枚举 $mask$：$O(2^M) = O(64)$
对每个 $mask$ 遍历所有字符串 $N \le 5\times 10^4$，并提取编码（$O(M)$），总 $O(2^M \cdot N \cdot M) \approx 64 \times 5\times 10^4 \times 6 \approx 2\times 10^7$，可行。
哈希表操作总体也是这个量级。

---

总结

本题利用 $M$ 很小的条件，通过状态压缩和容斥原理，将字符串匹配问题转化为集合分类计数问题。
关键点：

1. 两个字符串能匹配当且仅当在它们都确定字母的位置上字母相同。
2. 枚举公共确定字母集合 $mask$，统计在该 $mask$ 上字母相同的字符串对数。
3. 用容斥去掉重复计数，得到恰好以 $mask$ 为最大公共确定字母集的对数。
4. 求和即得答案。

时间复杂度 $O(2^M \cdot N \cdot M)$，在给定范围内可行。