​
题意：
给定一个n个点的图形，每两点之间都有连线，线的颜色有白色和黑色两种，题目给了计算黑白边的算法，求三条边颜色都相同的三角形的个数。
注：这一题数据给的小于8000的数据范围，且计算黑白边的算法题目给的复杂度是O(n),意味着这道题最大的复杂度不能超过O(n)，这意味着暴力算法行不通（暴力的复杂的为O(n)）。

思考：
首先，边的颜色只有黑白两种，所以对于一个三条边不全相同颜色的三角形来说，一定有两条边是一样颜色的，而且它的三个角中有一个角是由两条颜色相同的边构成的（同色角），两个角是由两条颜色不同的边构成的（异色角）。所以推出：同色三角形的个数=总三角形个数-异色三角形个数。以一个点为例，图形中从一个点出发有n-1条边，如果有num条黑边，则有num-n-1条白边。从一个点出发构成异色三角形个数=黑边数白边数/2。
如果忽略边的颜色，对于一个有n个点而且每两个点之间都有连线的图形来说，任意挑三个点出来就可以组成一个三角形，所以n个点可以构成三角形数量为C，也就是n(n-1)*(n-2)/6个。
注：在计算三角形数量时候需要强制类型转换，否则会超范围。

include

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 std;
using namespace GenHelper;
bool edge[8005][8005];

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();
}
long long num,ans = 0;
for(int i = 0;i<n;i++){
num = 0;
for(int j = 0;j<n;j++){
if(edge[i][j]) num++;
}
ans+=num(n-num-1);//计算从点i出发构成的异色三角形数量
}
cout << (long long)n(n-1)*(n-2)/6-ans/2 << endl;//在此处需要强制类型转换，否则会超范围
return 0;
}

​