题解：AT_abc483_e [ABC483E] Typo Pairs

· · 题解

思路

可以枚举有 C_n^{m - 2} 的所有可能性，求出 m - 2 个位置相等的字符串的个数，设每个枚举的位置相同，字符相同的点的个数为 cnt，则有 (cnt - 1) + (cnt - 2) + \dots + 1 种组合，化简为 \frac{cnt \cdot (cnt - 1)}{2}。但是有重复相加的，就是令两个字符串的下标分别为 i, j，满足 1 \le i \le n,i + 1 \le j \le n，对于 1 \le k \le m 满足 S_{i, k} \neq S_{j,k} 的个数不大于 1，这样的字符串就是相加多了的，需要减去多的部分，也就是 m - 2 个搭配的可能数，最后加上多减去的部分，为 \frac{(m - 1)\cdot (m - 2)}{2} 个相同的字符串个数可能值。

Code

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

#define int long long

string s[200005];

vector<int> a;

bool nxt(int n, int k)
{
    int i = k - 1;
    while(i >= 0 && a[i] == n - k + i) i--;
    if(i < 0) return false;
    a[i]++;
    for(int j = i + 1; j < k; j++)
        a[j] = a[j - 1] + 1;
    return true;
}

map<string, int> mp;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> s[i], mp[s[i]]++;

    //由于不太可能直接定义 m - 1 维的数组，由于 m 很小，我们可以直接枚举 m 的所有可能性
    if(m == 6)
    {
        a.resize(4);
        for(int i = 0; i < 4; i++) a[i] = i;
        vector<vector<vector<vector<vector<int> > > > > cnt1;
        vector<vector<vector<vector<int> > > > cnt2;
        cnt1.resize(26, vector<vector<vector<vector<int> > > >(26, vector<vector<vector<int> > >(26, vector<vector<int> >(26, vector<int>(26, 0)))));
        cnt2.resize(26, vector<vector<vector<int> > >(26, vector<vector<int> >(26, vector<int>(26, 0))));
        int sum = 0;
        do
        {
            for(int i = 1; i <= n; i++) cnt2[s[i][a[0]] - 'a'][s[i][a[1]] - 'a'][s[i][a[2]] - 'a'][s[i][a[3]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++) for(int l = 0; l < 26; l++)
                sum += (cnt2[i][j][k][l] - 1) * cnt2[i][j][k][l] / 2, cnt2[i][j][k][l] = 0;
        }
        while(nxt(6, 4));
        a.resize(5);
        for(int i = 0; i < 5; i++) a[i] = i;
        do
        {
            for(int i = 1; i <= n; i++) cnt1[s[i][a[0]] - 'a'][s[i][a[1]] - 'a'][s[i][a[2]] - 'a'][s[i][a[3]] - 'a'][s[i][a[4]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++) for(int l = 0; l < 26; l++) for(int mm = 0; mm < 26; mm++)
                sum -= (cnt1[i][j][k][l][mm] - 1) * cnt1[i][j][k][l][mm] * 2, cnt1[i][j][k][l][mm] = 0; //把除以 2 抵消了，变为乘 2
        }
        while(nxt(6, 5));

        for(auto [str, cnt] : mp)
            sum += 10 * cnt * (cnt - 1) / 2;

        cout << sum << '\n';
    }
    if(m == 5)
    {
        a.resize(3);
        for(int i = 0; i < 3; i++) a[i] = i;
        vector<vector<vector<vector<int> > > > cnt1;
        vector<vector<vector<int> > > cnt2;
        cnt1.resize(26, vector<vector<vector<int> > >(26, vector<vector<int> >(26, vector<int>(26, 0))));
        cnt2.resize(26, vector<vector<int> >(26, vector<int>(26, 0)));
        int sum = 0;
        do
        {
            for(int i = 1; i <= n; i++) cnt2[s[i][a[0]] - 'a'][s[i][a[1]] - 'a'][s[i][a[2]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++)
                sum += (cnt2[i][j][k] - 1) * cnt2[i][j][k] / 2, cnt2[i][j][k] = 0;
        }
        while(nxt(5, 3));
        a.resize(4);
        for(int i = 0; i < 4; i++) a[i] = i;
        do
        {
            for(int i = 1; i <= n; i++) cnt1[s[i][a[0]] - 'a'][s[i][a[1]] - 'a'][s[i][a[2]] - 'a'][s[i][a[3]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++) for(int l = 0; l < 26; l++)
                sum -= (cnt1[i][j][k][l] - 1) * cnt1[i][j][k][l] / 2 * 3, cnt1[i][j][k][l] = 0;
        }
        while(nxt(5, 4));

        for(auto [str, cnt] : mp)
            sum += 6 * cnt * (cnt - 1) / 2;

        cout << sum << '\n';
    }
    if(m == 4)
    {
        a.resize(2);
        for(int i = 0; i < 2; i++) a[i] = i;
        vector<vector<vector<int> > > cnt1;
        vector<vector<int> > cnt2;
        cnt1.resize(26, vector<vector<int> >(26, vector<int>(26, 0)));
        cnt2.resize(26, vector<int>(26, 0));
        int sum = 0;
        do
        {
            for(int i = 1; i <= n; i++) cnt2[s[i][a[0]] - 'a'][s[i][a[1]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++)
                sum += (cnt2[i][j] - 1) * cnt2[i][j] / 2, cnt2[i][j] = 0;
        }
        while(nxt(4, 2));
        a.resize(3);
        for(int i = 0; i < 3; i++) a[i] = i;
        do
        {
            for(int i = 1; i <= n; i++) cnt1[s[i][a[0]] - 'a'][s[i][a[1]] - 'a'][s[i][a[2]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++)
                sum -= (cnt1[i][j][k] - 1) * cnt1[i][j][k], cnt1[i][j][k] = 0; //除以 2 和乘 2 抵消了
        }
        while(nxt(4, 3));

        for(auto [str, cnt] : mp)
            sum += 3 * cnt * (cnt - 1) / 2;

        cout << sum << '\n';
    }
    if(m == 3)
    {
        a.resize(1);
        for(int i = 0; i < 1; i++) a[i] = i;
        vector<vector<int> > cnt1;
        vector<int> cnt2;
        cnt1.resize(26, vector<int>(26, 0));
        cnt2.resize(26, 0);
        int sum = 0;
        do
        {
            for(int i = 1; i <= n; i++) cnt2[s[i][a[0]] - 'a']++;
            for(int i = 0; i < 26; i++)
                sum += (cnt2[i] - 1) * cnt2[i] / 2, cnt2[i] = 0;
        }
        while(nxt(3, 1));
        a.resize(2);
        for(int i = 0; i < 2; i++) a[i] = i;
        do
        {
            for(int i = 1; i <= n; i++) cnt1[s[i][a[0]] - 'a'][s[i][a[1]] - 'a']++;
            for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++)
                sum -= (cnt1[i][j] - 1) * cnt1[i][j] / 2, cnt1[i][j] = 0;
        }
        while(nxt(3, 2));

        for(auto [str, cnt] : mp)
            sum += cnt * (cnt - 1) / 2;

        cout << sum << '\n';
    }
    if(m == 2)
        cout << n * (n - 1) / 2 << '\n'; //所有字符串都能互相匹配

    return 0;
}