连通三元组

题意解析

我们使用 $A_i$ 的二进制位来表示 $i$ 和其他点之间是否有边。

为了方便运算，我们可以只存储编号较小的点到编号较大点的边。

当 $i$ 和 $j$ 固定不变时，满足条件的 $k$ 的个数即 $A_{i,k}=A_{j,k}=1$ 的个数，即 $A_i\ \mathrm{AND}\ A_j$ 中 $1$ 的个数。

因此，我们可以使用 std::bitset 来实现
$A_1,A_2,\dots,A_N$ 并枚举 $(i,j)$ 计算 $A_i\ \mathrm{AND}\ A_j$ 中的 $1$ 个数，总共需要 $O(\frac{N}{w})$ 时间其中 $w = 64$，因此总的时间复杂度为 $\mathrm{O}(\frac{N^3}{w})$。

由于 $\frac{3000^3}{64}=421875000 \simeq 4 \times 10^8$ ，这个解法已经足够快了。我们只需枚举 $i,j(i < j)$ 就能进一步将执行时间减半。

AC代码

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

using i64 = long long;

constexpr int N = 3000;

bitset<N> st[N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (g[i][j] == '1') st[i][j] = 1;
    i64 res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j + 1 < n; ++j)
            if (st[i][j])
                res += (st[i] & st[j]).count();
    cout << res << '\n';
    return 0;
}