C++ 位集算法

Question

我得到了一个填充为 1 或 0 的 nxn 网格。我想计算角块全为 1 的子网格的数量。我的解决方案遍历所有行对并计算匹配 1 的数量，然后使用公式 numOf1s * (numOf1s-1)/2 并添加到结果中。但是，当我在 https://cses.fi/problemset/task/2137 上提交我的解决方案时，n = 3000 的输入上没有输出(可能由某些错误引起)。错误可能是什么？

int main()
    {
    
        int n; cin>> n;
        vector<bitset<3000>> grid(n);
        for(int i=0;i<n;i++){
            cin >> grid[i];
        }
        long result = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int count = (grid[i]&grid[j]).count();
                result += (count*(count-1))/2;
            }
        }
        cout << result;
    }

Answer 1

此解决方案将导致超出时间限制。 bitset::count() 在最坏的情况下是 O(n)。代码的总复杂度为 O(n^3)。在最坏的情况下，操作次数将是 3000^3 > 10^10，这太大了。