卡 bitset 计数的常（仅非位移运算）

前两天模拟赛有一道神秘题目可以使用 bitset 获得 30 分。

但是通过某些方式我获得了 50 分，这是因为 STL 提供的 bitset 相对低效，因此在赛场上重新发明了 bitset！（x

这道题是这样的：

for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (check(re[i], re[j])) {
            flag[i][j] = 1;
            res[rcnt++] = { i, j };
        }
    }
}

long long ans = 0;
for (int p = 0; p < rcnt; p++) {
    int i = res[p].first, j = res[p].second;
    ans += (flag[i] & flag[j]).count();
}

在 n = 8000 的某组数据用时 ~25s。

于是想，能不能稍微优化一下呢？就算是尽量减少 bitset 的常数也可以啊（例如两个 bitset 运算产生的临时对象）。然后发现，手写 bitset 好像也不是那么难。

long long fl[MAXN][128];

for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (check(re[i], re[j])) {
            fl[i][j / 64] |= 1ll << (j % 64); // 编译器会帮我们优化成位运算
            res[rcnt++] = { i, j };
        }
    }
}

long long ans = 0;

for (int p = 0; p < rcnt; p++) {
    int i = res[p].first, j = res[p].second;
    for (int x = 0; x < 128; x++) {
        ans += __builtin_popcountll(fl[i][x] & fl[j][x]);
    }
}

本机测试的时间来到了 10s！有进步。还有优化的空间吗？有。

发现，对于所有 j，j 这一位之前都是 0，可以不需要计算。所以我们这么改：

for (int p = 0; p < rcnt; p++) {
    int i = res[p].first, j = res[p].second;
    for (int x = j / 64; x < 128; x++) {
        ans += __builtin_popcountll(fl[i][x] & fl[j][x]);
    }
}

时间来到了 4.5s。鉴于这道题时限非常大（5s+），所以我们可以拿到这部分的分数。