题解：AT_abc483_e [ABC483E] Typo Pairs

lcliruiyan · 2026-11-10 13:54:54 · 题解

题目传送门

题目思路

首先，很容易想到，如果两个字符串的汉明距离为 k，那么将所有不相同的一对位置全部赋值为一个通配符后，这两个新字符串一定是相等的，下文将这种新字符串称为两个原字符串的模板串。

首先有一个比较暴力的思路，对于每一个字符串，我们可以先生成与这个字符串汉明距离为 0、1、2 的模板串，统计每一个模板串的出现次数，最后遍历所有出现过的模板串，计算出匹配的总次数即可。由于字符串长度非常小，这样做也不会超时。

但是，同一对字符串可能会被多次匹配。举个例子，如果两个字符串完全相同，那么这两个字符串的所有模板串都会匹配。所以，我们需要对匹配对数去重。

首先，我们设 x_0 表示实际上汉明距离为 0 的字符串对数，x_1 表示实际上汉明距离为 1 的字符串对数，x_2 表示实际上汉明距离为 2 的字符串对数。再设 f_0 表示计算出的汉明距离为 0 的字符串对数，f_1 表示计算出的汉明距离为 1 的字符串对数，f_2 表示计算出的汉明距离为 2 的字符串对数。

接下来，分别对三种情况分类讨论。

若汉明距离为 0，则计算出距离为 0 的个数就等于实际个数，其他距离不会被匹配，一定都为 0。

若汉明距离为 1，那么计算出的距离为 1 的个数等于总位数乘以实际上距离为 0 的个数再加上实际上距离为 1 的个数。

同理，若汉明距离为 2，那么计算出的距离为 2 的个数等于在串中选择两个位置的方案数乘以实际上距离为 0 的个数，再加上去除这一位后的总位数乘以实际上距离为 1 的个数再加上实际上距离为 2 的个数。

设字符串的长度为 m，那么有以下三条公式：

然后将这三个等式分别解出来即可，只需要简单的运算，此处省略。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
unordered_map<string,int>cnt0,cnt1,cnt2;
string s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); 
    cin>>n>>m;
    int f0=0,f1=0,f2=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int mask=0;mask<(1<<m);mask++){
            int b=__builtin_popcount(mask);
            if(b>2)continue;
            string t=s;
            for(int p=0;p<m;p++)
                if(mask>>p&1)t[p]='*';
            if(b==0)f0+=cnt0[t],cnt0[t]++;
            if(b==1)f1+=cnt1[t],cnt1[t]++;
            if(b==2)f2+=cnt2[t],cnt2[t]++;
        }
    }
    int c1=m*(m-1)/2;
    int ans0=f0;
    int ans1=f1-m*ans0;
    int ans2=f2-c1*ans0-(m-1)*ans1;
    cout<<ans0+ans1+ans2;
    return 0;
}