\(\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;
}