通过状压把每个数分为 1024 类中的一种

暴力枚举所有的类组成的对

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[1024]; // cnt[i] 统计状态 i 出现了几次
string s;
// 计算 s 中包含数字的状态压缩
int cal()
{
    int sta = 0;
    for (int i = 0; i < s.size(); i++)
    {
        // 第 i 位的整数
        int now = s[i] - '0';
        sta = (sta | (1 << now));
    }
    return sta;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        cnt[cal()]++;
    }
    long long ans = 0;
    for (int i = 0; i < 1024; i++)
    {
        ans += (long long)cnt[i] * (cnt[i] - 1) / 2;
        for (int j = i + 1; j < 1024; j++)
            if (i & j)
                ans += (long long)cnt[i] * cnt[j];
    }
    cout << ans << "\n";
    return 0;
}

无聊的容斥

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[1024]; // cnt[i] 统计状态 i 出现了几次
string s;
// 计算 s 中包含数字的状态压缩
int cal()
{
    int sta = 0;
    for (int i = 0; i < s.size(); i++)
    {
        // 第 i 位的整数
        int now = s[i] - '0';
        sta = (sta | (1 << now));
    }
    return sta;
}
// 计算 x 二进制含有几个 1
int cnt1(long long x)
{
    int res = 0;
    while (x)
        res++, x -= (x & -x);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        cnt[cal()]++;
    }
    long long ans = 0;
    // 容斥，处理同时包含了 sta 这些数字的状态
    for (int sta = 1; sta < 1024; sta++)
    {
        long long sum = 0; // 处理有多少种
        for (int i = 1; i < 1024; i++)
            if ((i & sta) == sta)
            {
                sum += cnt[i];
            }
        if (sum == 0)
            continue;

        int temp = cnt1(sta);

        if (temp % 2 == 1)
            ans += sum * (sum - 1) / 2;
        else
            ans -= sum * (sum - 1) / 2;
    }
    cout << ans << "\n";
    return 0;
}