LYDSY模拟赛day1 Tourist Attractions

/*

假设路径是 a − b − c − d，考虑枚举中间这条边 b − c，计

算有多少可行的 a 和 d。

设 degx 表示点 x 的度数，那么边 b − c 对答案的贡献为

(degb − 1)(degc − 1)− 经过 b − c 这条边的三元环个数。

计算三元环的个数只需要枚举除 b; c 之外的另一个点即可。

位运算优化

*/

#include<cstdio>

const int N=;

int cnt[],m,n,i,j,d[N];char g[N][N];long long ans;

int popcount(unsigned int x){return cnt[x>>]+cnt[x&];}

struct BIT{

  unsigned int v[];

  void set(int x){v[x>>]|=1U<<(x&);}

  void count(const BIT&b){for(int i=;i<=m;i++)ans-=popcount(v[i]&b.v[i]);}

}f[N];

int main(){

  freopen("tour.in","r",stdin);freopen("tour.out","w",stdout);

  for(i=;i<;i++)cnt[i]=cnt[i>>]+(i&);

  scanf("%d",&n);m=(n-)>>;

  for(i=;i<n;i++){

    scanf("%s",g[i]);

    for(j=;j<n;j++)if(g[i][j]=='')f[i].set(j),d[i]++;

  }

  for(i=;i<n;i++)for(j=;j<i;j++)if(g[i][j]=='')ans+=(d[i]-)*(d[j]-),f[i].count(f[j]);

  printf("%I64d",ans*);

  fclose(stdin);fclose(stdout);

  return ;

}