题解 [ABC258G] Triangle

题目链接

\(\rm O(n^3)\) 枚举 \(i,j,k\) 的算法是显然的。

考虑优化掉一个 \(n\)，如果枚举 \(i,j\)，那么显然需要找出有多少个 \(k\) 同时满足 \(a_{i,k}=a_{j,k}=1\)，我们可以将 \(a_i\) 和 \(a_j\) 看作两个二进制数，那么同时等于 \(1\) 的位置就是并起来等于 \(1\) 的位置，\(bitset\) 维护即可。

那么 \(i<k,j<k\) 的条件，只需要在 \(bitset\) 中维护 \(i\) 后面的位即可。

代码：

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

typedef long long LL;
LL read() {
    LL sum=0,flag=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=3100;
int n,m;
string s[N];
bitset<N> a[N];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>s[i]; s[i]=" "+s[i];
        for(int j=i+1;j<=n;j++) if(s[i][j]=='1') a[i][j]=1;
    }
    LL ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            if(s[i][j]=='1') {
                ans+=(a[i]&a[j]).count();
            }
        }
    }
    cout<<ans;
    return 0;
}