原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个具体值
1.2 题目背景、允许、禁止与限制
背景：
有 nnn 个长度为 mmm 的参数化单词
> 参数化单词：只包含小写字母和问号的单词
允许：
> 两个参数化单词是相似的，当且仅当通过使用小写字母替换问号可以使它们完全相同
求有多少对参数化单词是相似的
1.3 题目数据范围与猜测
n≤5×104,m≤6⟶O(nm)n \le 5\times 10^4,m\le 6\longrightarrow O(nm)n≤5×104,m≤6⟶O(nm)
1.4 一句话概括题意
求有多少组相似单词
2 题目破题推导
2.1 第一步：正向思维转逆向思维
正向：枚举所有字符对并进行一一匹配，时间复杂度 O(n2m)O(n^2m)O(n2m)
逆向：对于所有字符串，用一种方法经过一轮遍历筛出来所有和他相似的单词，猜测时间复杂度 O(nm)O(nm)O(nm)
2.2 第二步：大拆小小组大
拆：把“两个字符串相似”拆成 mmm 位分别考虑相似性
组：用二进制将 mmm 位上的 ??? 和 a∼za\sim za∼z 都压缩
2.3 第三步：分情况讨论
对于每个字符串，初始认为所有字符串（包括它自己）和它都可以匹配上（为 111），遍历 mmm 位
* 当前这一位是 ???，不管，该是 111 还是 111，该是 000 还是 000
* 当前这一位是小写字母 ccc，对方这一位必须也是 ccc 或者 ???，否则就变成了 000
最后只有还为 111 的位置才说明与其能成为相似单词
2.4 第四步：边界思想
那么现在我们通过一轮 O(nm)O(nm)O(nm) 时间复杂度的遍历得到了一些二进制串（当然每轮结束后会被覆盖）
第 iii 串代表第 iii 个字符串与其他字符串全部 mmm 位上的匹配情况
比如串有这些（举个例子，每次开始遍历新字符串会覆盖）
那么答案应该如何计算呢？
答案是累加一个变量ans
对于每个二进制串 sss，ans=ans+(count(s)−1)ans=ans+(count(s)-1)ans=ans+(count(s)−1)，最终答案是 ans÷2ans\div 2ans÷2
其中 count(x)count(x)count(x) 代表二进制串 xxx 中 111 的数量
* 为什么要 −1-1−1？
因为自己和自己永远能匹配上，但是问题要求找“两个参数化单词”组成一对，所以要减去自己的这一种
* 为什么最终要 ÷2\div 2÷2？
因为假如 (1,3)(1,3)(1,3) 能匹配上，则 (3,1)(3,1)(3,1) 也一定能匹配上
而我们要求“多少对”，肯定不能把它们算作两组
3 模型匹配
bitset可以快速解决很多位二进制的问题
4 最终代码（禁止抄袭，仅用于参考）
