2020.9.5
题目描述
有 \(n\) 个只包含 '\(x\)','\(y\)','\(z\)' 三种字符的字符串，长度均为 \(m\) ，且 \(n \cdot m \leq 10^5\) 。
现定义
\[\sum [A_i=B_i]
\]
为两字符串 \(A,B\) 的相似程度。求对于每个 \(i \in [0,m]\) ，相似程度为 \(i\) 的无序字符串对数有几对。
解法
暴力显然是 \(O(n^2m)\) 的，枚举两个字符串，暴力匹配累加答案，可以过大部分数据（？。
考虑 \(m\) 很小的情况，即 \(n^2\) 很大不可枚举。
由相同种类计数想到状压。对于一个字符串，可以转换为三进制数，然后按顺序每次改变一位，则相似程度减一，累加答案，复杂度最坏为 \(O(3^mm)\)，可以跑过剩下数据（？。
（数据太水不想吐槽了
Tips
第一次写三进制状压，记下笔记。
三进制显然不能像二进制一样方便地进行位运算。首先要预处理出 \(3\) 的所有幂，然后对于每一个状态，处理处它的每一位的值，记录在 \(dig[sta][j]\) 中。
p[0]=1;
for(int i=1;i<=m;i++) p[i]=p[i-1]*3;
for(int i=0;i<p[m];i++){
int tmp=i;
for(int j=0;j<m;j++){
dig[i][j]=tmp%3;
tmp/=3;
}
}