[at] ABC 258g - Triangle triples reachable - violence

Preface

$tag:$bitset01 chart
Portal :

The question :
Given a $01$ Complete graph ,$1$ Indicates that these two points are connected by edges ,$0$ It means that these two points have no edge connected

Ask how many groups of triples there are $(i,j,k)$, Meet the requirement that two sides are connected

Ideas :

Violent practices $n^3$, Because graphs only exist $01$, We consider using bit operations to subtract one level of enumeration

namely bitset , We store the status in biset in , Then enumerate the states between the two lines , Conduct $\&$ operation

Obviously, if $\&=1$ that , There are three points that can be reached , Time complexity $n^{2}logn$

code :

void solve(){
    
	int n;cin>>n;
	vector<bitset<N>> v(n);
	vector<string> s(n);
	
	for(int i = 0; i < n; i ++ ){
    
		cin>>s[i];
		
		for(int j = 0 ; j < n ; j ++ ){
    
			if(s[i][j] == '1') v[i][j] = 1;
		}
	}
	
	ll ans = 0 ;
	for(int i = 0 ; i< n ; i ++ ){
    
		for(int j = 0 ; j< i ; j ++ ){
    
			if(s[i][j] == '1') ans += (v[i]&v[j]).count();
		}
	}
	
	cout<<ans/3<<endl;
	
}

int main(){
    
	//int t;cin>>t;while(t--)
    solve();
    return 0 ;
}