题解：AT_past17_i 部分列ペア

· · 题解

题意很清晰了，就不多赘述了。

solution

不遍历所有 (i,j) 对判断子序列，而是对每个 S_j，枚举它的 所有唯一子序列 T，那么所有以 T 为 S_i 的字符串都能和 S_j 形成有效对 (i,j)。
::::info[如果你不太明白具体实现]{open} 我们对子序列进行二进制枚举即可。

对于长度为 L 的字符串，每个子序列可以用一个 L 位的二进制数表示：

每个字符串的子序列可能重复，需要先去重再统计。
::::info[如果你不太理解] 如 \mathtt{aa} 的子序列 \mathtt{a} 会被枚举两次。 ::::

用 mp 统计每个字符串的出现次数，对每个 S_j 的所有唯一子序列 T，累加 mp[T] 即可得到总答案。

AC code

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
string s[MAXN];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);    
    cin.tie(nullptr);cout.tie(nullptr);
    int n;
    cin>>n;
    map<string,int>mp;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        mp[s[i]]++;
    }
    long long ans=0;
    //遍历每个字符串s[i]，枚举其所有唯一子序列
    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];//第k位为1，选取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;
}

利用 |S_i|≤5 的特性，枚举每个字符串的所有子序列，将时间复杂度从 O(N^2) 降至 O(N \times 2^{\max ^{N}_{i=0}|S_i|})。