[数据结构与算法]牛客2021暑期训练3-J-Counting Triangles

牛客2021暑期训练3-J-Counting Triangles

题目链接

题意

给一个 n(n<=8000) 个顶点的图，每两个顶点边颜色为黑或白，求三个顶点组成的三角形边颜色相同的个数

题解

每个三?形要么同?，要么有两边同?另?边异?。对于后者，三?形有恰有两个异??，?前者没有异??。
因此异??数/2 即为不符合条件的三?个数。?总数减去即可。复杂度 n^2

代码

#include<bits/stdc++.h>
#define LL long long
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
    	u = 0;
    }
}
using namespace GenHelper;
using namespace std;
const int N=8009;
LL ans;
bool edge[8005][8005];
int v[N][2];

int main() {
	int n, seed;
	cin >> n >> seed;
	srand(seed);
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			edge[j][i] = edge[i][j] = read();
			v[i][edge[i][j]]++;
			v[j][edge[i][j]]++;
		}
	for(int i=0;i<n;i++)
		ans+=(LL)v[i][0]*(LL)v[i][1];
	cout<<(LL)n*(LL)(n-1)*(LL)(n-2)/6-ans/2<<endl;
	return 0;
}