本問で扱われる文字列は長さが短いため、本解説ではそれらの比較等が \(\mathrm{O}(1)\) で行えるものとします。
\(S_1,\dots,S_N\) の中にある文字列 \(T\) が何個含まれるかは、連想配列(C++ではmapとして提供されている)を用いることで \(\mathrm{O}(\log N)\) で取得できます。そこで、\(S_1,\ldots,S_N\) それぞれにおいて高々 \(2^{|S_i|}\) 個存在する部分列を全列挙し、mapを用いて何個ずつあるかを調べれば良いです。 ただし、aa のような文字列において a は部分列として \(2\) 回現れるため、重複して数えないために全列挙した部分列を相異なるようにする必要があることに気を付けてください(解答例では28・29行目でそのような処理を行っています)。

解答例(C++)

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

int main() {
    
	int N;
	cin>>N;
	
	vector<string> S(N);
	map<string,int> mp;
	
	for(int i=0;i<N;i++){
		cin>>S[i];
		mp[S[i]]++;
	}
	
	long long ans = 0;
	
	for(int i=0;i<N;i++){
		vector<string> ts;
		for(int j=0;j<(1<<S[i].size());j++){
			string t = "";
			for(int k=0;k<S[i].size();k++){
				if((j>>k)&1)t += S[i][k];
			}
			ts.push_back(t);
		}
		sort(ts.begin(),ts.end());
		ts.erase(unique(ts.begin(),ts.end()),ts.end());
		for(int j=0;j<ts.size();j++){
			if(mp.count(ts[j]))ans += mp[ts[j]];
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}