思路

bitset优化传递闭包模板。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=2007;

bitset<maxn>bi[maxn];
int n,ans=0;
string str;

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>str;
		for(int j=1;j<=n;j++)
			bi[i][j]=(str[j-1]=='1'||i==j)?1:0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(bi[j].test(i)) bi[j]|=bi[i];
	for(int i=1;i<=n;i++) ans+=bi[i].count();
	cout<<ans<<endl;
	return 0;
}