包除原理を用いてこの問題を解くことを考えます。

整数の組 \((i,j)\) \((1\leq i<j\leq N)\) であって、\(S_i\) と \(S_j\) が等しいもの、すなわちハミング距離が \(0\) のものの集合を \(A\) とします。
次に、\(1\leq k\leq M\) について、整数の組 \((i,j)\) \((1\leq i<j\leq N)\) であって、\(S_i\) と \(S_j\) が \(k\) 文字目以外すべて等しいもの（\(k\) 文字目は等しくても等しくなくても良い）集合を \(B_k\) とします。
最後に、\(1\leq k<k'\leq M\) について、整数の組 \((i,j)\) \((1\leq i<j\leq N)\) であって、\(S_i\) と \(S_j\) が \(k,k'\) 文字目以外すべて等しいもの（\(k,k'\) 文字目は等しくても等しくなくても良い）集合を \(C_{k,k'}\) とします。

さて、それぞれの \((i,j)\) \((1\leq i\leq j)\) が\(A,B_k,C_{k,k'}\) のうちのいくつに含まれるか考えます。

• \(S_i\) と \(S_j\) が完全に等しいとき

\((i,j)\) はすべての集合に含まれます。すなわち、\(A\)、\(B_1,B_2,\ldots,B_M\) のうち \(M\) 個、\(C_{1,2},\ldots,C_{M-1,M}\) のうち \(M(M-1)/2\) 個に含まれます。

• \(S_i\) と \(S_j\) が \(k\) 文字目のみ異なるとき

\((i,j)\) は \(A\) に含まれません。\((i,j)\) は \(B_1,B_2,\ldots,B_M\) のうち \(B_k\) のみに含まれます。\(C_{1,2},\ldots,C_{M-1,M}\) のうち 、\(C{1,k},\ldots, C{k-1,k}, C_{k,k+1},\ldots,C_{k,M}\) の\(M-1\) 個に含まれます。

• \(S_i\) と \(S_j\) が \(k,k'\) 文字目 \((k<k')\) のみ異なるとき

\((i,j)\) は \(A\) および \(B_1,B_2,\ldots,B_M\) に含まれません。また、\(C_{1,2},\ldots,C_{M-1,M}\) のうち 、\(C_{k,k'}\) にのみ含まれます。

• \(S_i\) と \(S_j\) が \(3\) 文字以上異なるとき

\((i,j)\) は \(A\)、\(B_1,B_2,\ldots,B_M\)、\(C_{1,2},\ldots,C_{M-1,M}\) のいずれにも含まれません。

さて、

\[ X=\frac{(M-1)(M-2)}{2}\lvert A\rvert-(M-2)\displaystyle\sum_{k=1}^M\lvert B_k\rvert+\displaystyle\sum_{k=1}^{M-1}\displaystyle\sum_{k'=k+1}^{M}\lvert C_{k,k'}\rvert\qquad \qquad (1) \]

という量を考えます。 ここで、集合 \(T\) に対して \(\lvert T\rvert\) で \(T\) の要素数を表します。 このとき、各 \((i,j)\) が何回数えられているか考えると、

• \(S_i\) と \(S_j\) が完全に等しいとき: \(\frac{(M-1)(M-2)}{2}\times 1-(M-2)\times M+1\times \frac{M(M-1)}{2}=1\)
• \(S_i\) と \(S_j\) が\(1\)文字のみ異なるとき: \(\frac{(M-1)(M-2)}{2}\times 0-(M-2)\times 1+1\times (M-1)=1\)
• \(S_i\) と \(S_j\) が\(2\)文字のみ異なるとき: \(\frac{(M-1)(M-2)}{2}\times 0-(M-2)\times 0+1\times1=1\)
• \(S_i\) と \(S_j\) が\(3\)文字以上異なるとき: \(\frac{(M-1)(M-2)}{2}\times 0-(M-2)\times 0+1\times 0=0\)

となるため、これは求めるべき答えと一致します。

\(\lvert A\rvert\) を求めるには、\(S_1,\ldots,S_N\) の中に各文字列が何個ずつ存在するかを数えれば良いです。すなわち、同じ文字列がそれぞれ \(x_1,x_2,\ldots, x_p\) 個ある \((1\leq x_i\), \(x_1+x_2+\cdots+x_p=N)\) とき、$\(\lvert A\rvert=\frac{x_1(x_1-1)}{2}+\frac{x_2(x_2-1)}{2}+\cdots+\frac{x_p(x_p-1)}{2}\) で求められます。 これは unorederd_map (C++) や dict (Python) で管理したり、\(S_1,S_2,\ldots, S_N\) をソートして尺取り法で数えるなどすることで求められます。

\(B_k, C_{k,k'}\) についても、\(k\) 文字目のみ、あるいは \(k,k'\) 文字目のみを除いた文字列について同様のことを行えば良いです。

計算量は実装によって異なりますが、\(O(NM^3)\) または \(O(NM^2(M+\log N))\)などになります。
よって、この問題を解くことができました。

なお、\((1)\) 式の右辺の係数については、各 \((i,j)\) が \(A, B_k,C_{k,k'}\) にいくつずつ含まれているかという情報から、ちょうど \(1\) 回ずつカウントされるように逆算することが可能です。　

c++による実装例;

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(ll i = 0; i < n; ++i)

int main(void){
	long long n,m;
	vector<long long>a;
	long long x,y,z,ans=0;

	cin>>n>>m;
	
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];

	for(int i=0;i<m;i++){
		for(int j=0;j<=i;j++){
            unordered_map<string,long long>mp;
			for(int k=0;k<n;k++){
				string tmp="";
				for(int ii=0;ii<m;ii++){
					if((ii==i)||(ii==j))continue;
					tmp+=s[k][ii];
				}
                mp[tmp]=mp[tmp]+1;
			}
			z=0;

            unordered_map<string,long long>::iterator itr=mp.begin();
			while(itr!=mp.end()){
                y=(*itr).second;
				z+=(y*(y-1))/2;
                itr++;
			}
			
			if(i!=j)ans+=z;
			else ans-=(m-2)*z;
		}
	}

    unordered_map<string,long long>mp;
    for(int k=0;k<n;k++)mp[s[k]]+=1;

    z=0;
    unordered_map<string,long long>::iterator itr=mp.begin();
    while(itr!=mp.end()){
        y=(*itr).second;
        z+=(y*(y-1))/2;
        itr++;
    }
	ans+=(m-1)*(m-2)/2*z;

	cout<<ans<<endl;
	return 0;
}