[at] ABC 258g - triple Reach - violence

Préface

$tag:$bitset01Fig.
Porte de transfert:

Titre :
Compte tenu d'un$01$Graphique complet,$1$Cela signifie que les deux points ont des bords reliés,$0$Ça veut dire qu'il n'y a pas de bords reliant ces deux points

Demandez combien de triples il y a$(i,j,k)$,Il y a des bords qui relient les deux

Idées :

Pratiques violentes$n^3$,Parce que le graphique n'existe que$01$,Nous envisageons d'utiliser des opérations de bits moins une couche d'énumération

C'est - à - dire:bitset , Nous mettons l'état dansbisetMoyenne,Puis énumérez les états entre les deux lignes,En cours$\&$Opération

Apparemment, si$\&=1$Alors,Trois points sont accessibles,Complexité temporelle$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 ;
}