思路

要求求每个点能到达的点数就是传递闭包

然后n^3Floyd可做，但是n=2000，然后bitset压位

复杂度\(O(\frac{n^3}{32})\)，能过

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;bitset<2010> S[2010];int n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ char c=getchar(); while(c!='0'&&c!='1') c=getchar(); if(i==j) S[i][j-1]=1; else S[i][j-1]=c-'0'; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(S[i][j-1]) S[i]|=S[j]; } int ans=0; for(int i=1;i<=n;i++) ans+=(S[i].count()); printf("%d\n",ans); return 0;}/*30100011009*/