2021牛客暑期多校训练营3 J题 Counting Triangles

题目描述

Goodeat finds an undirected complete graph with n vertices. Each edge of the graph is painted black or white. He wants you to help him find the number of triangles (a, b, c) (a < b < c), such that the edges between (a, b), (b, c), (c, a) have the same color. To avoid the input scale being too large, we use the following code to generate edges in the graph.

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;
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();
     return 0;
}

The $edge$ array in the above code stores the color of the edges in the graph. $edge[i][j]=1$ means that the edge from i to j is black, otherwise it is white ($\forall 0 \le i \neq j \le n-1$).

Ensure that there is an approach that does not depend on the way the data is generated.

输入描述:

The first line contains two integers $n(n \le 8000), seed (seed \le 10^9)$, denote the number of vertices and the seed of random generator.

输出描述:

Output a line denoting the answer.

示例1

输入

10 114514

输出

35

说明

There're 35 triangles that all three edges have the same color.

题解

这一题是一道思维规律题。题目大致意思是给你一个无向完全图，然后将边分为黑色和白色，求解其中有多少个三条边是一种颜色的三元环。

这个无向图是一个完全图也是一个二分图，所以我们可以比较简单的求出其中三条边不是一种颜色的三元环。例如：

A点有2条黑色边（实线）和3条白边（虚线），这样我们可以得知与A点相连的边无法构成$6(2*3)$个三条边是一种颜色的三元环（可以轻易证明出来）。同时我们知道无法构成三条边是一种颜色的三元环只有以下两种情况：

1. 三条边分别为黑、黑、白。
2. 三条边分别为黑、白、白。

所以与一个点相连的其他点所得到无法构成三条边是一种颜色的三元环会重复有且只有一次。

然后我们求出无向图中所有的三元环数量为：$n*(n-1)*(n-2)/6$ 。

我们用无向图中所有的三元环数量减去无法构成三条边是一种颜色的三元环数量，便可以得到三条边是一种颜色的三元环数量。

代码

代码如下：

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 8e3 + 10;
typedef long long ll;

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


ll vis1[maxn];
ll vis0[maxn];
ll ans;
int main() {
  int n, seed;
  cin >> n >> seed;
  srand(seed);
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      edge[j][i] = edge[i][j] = read();
      if (edge[j][i]) {
        vis1[i]++;
        vis1[j]++;
      }    
      else {
        vis0[i]++;
        vis0[j]++;
      }   
    }
  for (int i = 1; i <= n; i++) {
    ans -= vis1[i] * vis0[i];
  }
  ans /= 2;
  ans += (ll)n * (n - 1) * (n - 2) / 6;
  cout << ans;
  return 0;
}