有一说一这题和 SDOI2013 spring 几乎完全一致。

方便起见，$d\leftarrow n-d$，也即询问恰有 $d$ 处相同的字符串有几对。

设指标全集 $U=\{1,2,3,4\}$。

定义恰好在 $S\subseteq U$ 指标集合中对应位字符相同，其余位均不同的字符串有 $f_S$ 对。

定义在 $S\subseteq U$ 指标集合中对应位字符相同的字符串有 $g_S$ 对。

根据定义，我们枚举 $g_S$ 的构成，得到

$$g_S=\sum_{S\subseteq T\subseteq U}f_T$$

由子集反演，我们得到

$$f_S=\sum_{S\subseteq T\subseteq U}(-1)^{|T|-|S|}g_T $$

而答案即为

$$\sum_{|S|=d}f_S=\sum_{|S|=d}\sum_{S\subseteq T\subseteq U}(-1)^{|T|-|S|}g_T\\=\sum_{T}(-1)^{|T|-|S|}\binom{|T|}dg_T $$

于是只用计算出每个 $g_S$ 即可。

这个就十分轻松了，我们枚举 $S$，然后提取 $n$ 个串中对应位，只用找到每一种模式串各有多少对即可。

这个可以排个序，也可以开个桶记录一下，怎么做都行。

以下是代码。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
inline uint turn(chr c){return c<='9'?c^'0':10+(c-'a');}
inline uint get(chr*C,uint S){
    uint ans=0;
    if(S&1)ans+=turn(C[0]);
    if(S&2)ans+=turn(C[1])*36;
    if(S&4)ans+=turn(C[2])*36*36;
    if(S&8)ans+=turn(C[3])*36*36*36;
    return ans;
}
const uint Binom[5][5]={{1,0,0,0,0},{1,1,0,0,0},{1,2,1,0,0},{1,3,3,1,0},{1,4,6,4,1}};
chr C[50005][5];uint A[50005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint n,d;scanf("%u%u",&n,&d),d=4-d;
    for(uint i=0;i<n;i++)scanf("%s",C[i]);
    uint ans=0;
    for(uint S=0;S<16;S++){
        uint b=__builtin_popcount(S);if(b<d)continue;
        for(uint i=0;i<n;i++)A[i]=get(C[i],S);
        std::sort(A,A+n);
        uint wil=0;
        for(uint i=0,v=0,w=0;i<n;i++)wil+=A[i]==w?v:(w=A[i],v=0),v++;
        if((b^d)&1)ans-=wil*Binom[b][d];
        else ans+=wil*Binom[b][d];
    }
    printf("%u\n",ans);
    return 0;
}