题解：AT_abc483_e [ABC483E] Typo Pairs

zhangruotian · 2026-11-12 09:38:59 · 题解

题目

AT

思路

观察发现，m 非常小，即每个字符串的长度都非常小。而且合法的一对字符串汉明距离不超过 2，说明这两个字符串最多有两个位置字符不同，那么我们可以枚举哪两个位置不同，然后去看剩下的位置是否相同，然后统计对数。

但是显然会得到比答案更大的答案。

我们令 c_0 表示有多少对字符串汉明距离为 0，c_1 表示有多少对字符串汉明距离不超过 1。

然后我们发现 c_1 里面包含了 c_0，然后 c_1 里面多算了 m 次 c_0，所以令 p_1 表示有多少对字符串汉明距离恰好为 1。有：

同样的，设 c_2 表示有多少对字符串汉明距离不超过 2。

经过观察，c_0 在 c_2 里面计算了 \binom m 2 次，p_1 在 c_2 里面计算了 m-1 次。那么令 p_2 表示有多少对字符串汉明距离恰好为 1。有：

所以最终答案即为：

化简，得：

完结撒花！

::::success[AC记录]

// Copyright 2026 (C) FFT_lg2
//All rights reserved
#include<bits/stdc++.h>
using namespace std;

#define int long long
template<class T>
void gmax(T &x,T y){x=max(x,y);}
template<class T>
void gmin(T &x,T y){x=min(x,y);}

void solve(){
    int n,m;cin>>n>>m;
    vector<string> s(n+1);
    for(int i=1;i<=n;i++) cin>>s[i],s[i]=' '+s[i];
    int ans1=0,ans2=0,ans0=0;
    for(int i=1;i<=m;i++){
        for(int j=i+1;j<=m;j++){
            vector<string> tmp(n+1);
            for(int k=1;k<=n;k++){
                //1~i-1 i+1~j-1 j+1~m
                //i-1-1+1 j-1-i-1+1 m-j-1+1
                //i-1 j-i-1 m-j
                if(i>=2) tmp[k]+=s[k].substr(1,i-1);
                if(j-i>=2) tmp[k]+=s[k].substr(i+1,j-i-1);
                if(m-j>=1) tmp[k]+=s[k].substr(j+1,m-j);
            }
            sort(tmp.begin()+1,tmp.end());
            int l=1,r=1;
            while(l<=n){
                while(r<=n&&tmp[r]==tmp[l]) r++;
                int len=r-l;
                ans2+=len*(len-1)/2,l=r;
            }
        }
    }
    for(int i=1;i<=m;i++){
        vector<string> tmp(n+1);
        for(int j=1;j<=n;j++){
            //1~i-1 i+1~m
            //i-1-1+1 m-i-1+1
            //i-1 m-i
            if(i>=2) tmp[j]+=s[j].substr(1,i-1);
            if(m-i>=1) tmp[j]+=s[j].substr(i+1,m-i);
        }
        sort(tmp.begin()+1,tmp.end());
        int l=1,r=1;
        while(l<=n){
            while(r<=n&&tmp[r]==tmp[l]) r++;
            int len=r-l;
            ans1+=len*(len-1)/2,l=r;
        }
    }
    sort(s.begin()+1,s.end());
    int l=1,r=1;
    while(l<=n){
        while(r<=n&&s[r]==s[l]) r++;
        int len=r-l;
        ans0+=len*(len-1)/2,l=r;
    }
    int p1=ans1-m*ans0;
    cout<<ans2-(m*(m-1)/2-1)*ans0-(m-2)*p1<<endl;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
}

::::