AT_abc483_e 题解

lonys · 2026-11-08 21:00:13 · 题解

AT_abc483_e 题解

分析

假设我们知道了两个字符串哪些位置不同，如何判断剩下的位置全部相同呢？

显然，我们可以将不同的位置全部修改成相同的字符，再判断是否相等即可。

进行分类讨论，显然，符合要求的汉明距离只有 0 或 1 或 2。

对于修改后的字符串，用哈希表统计出现次数 c_i，那么对数就是 c_i\choose 2，即 \frac{c_i\times(c_i-1)}{2}。

显然，可以枚举哪些位置不同，进行修改，然后用上述方法进行统计。

那么我们需要将他们进行去重。

• 如果有 0 个位置不同，则不需要去重。
• 如果有 1 个位置不同，那么 0 个位置不同的会被多算，每一对字符串会被多算 m 次。
• 如果有 2 个位置不同，分两种情况：

这样，我们就得到了每个汉明距离的对数，相加即可。

代码实现

::::success[参考代码]{open}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int c0,c1,c2;
string s[200010];
string t[200010];
inline int count(){
    int ans=0;
    unordered_map<string,int>mp;
    for(int i=1;i<=n;i++){
        mp[t[i]]++;
    }
    for(auto i:mp){
        ans+=i.second*(i.second-1)/2;
    }
    return ans;
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=' '+s[i];
        t[i]=s[i];
    }
    c0=count();
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            t[j]=s[j];
            t[j][i]='z';
        }   
        c1+=count();
    }
    for(int i=1;i<=m;i++){
        for(int j=i+1;j<=m;j++){
            for(int k=1;k<=n;k++){
                t[k]=s[k];
                t[k][i]='z';
                t[k][j]='z';
            }
            c2+=count();
        }
    }
    c1-=c0*m;
    c2-=c0*m*(m-1)/2;
    c2-=c1*(m-1);
    cout<<c0+c1+c2;
    return 0;
}

::::