【牛客训练记录】2024牛客国庆集训派对day1

https://ac.nowcoder.com/acm/contest/90188#question

赛后反思

好像没有，全场只做出来一题 QAQ

J题

想在图上找到同色三角形，我们枚举至少是 \(O(n^3)\) 的，所以我们考虑容斥定理(?)，去找异色三角形，因为只要保证一条边上两点颜色不一样，另找一点随便都可以，所以我们只要统计白色的点数，每个点可以有 \((n-1-siz[i])\)（黑色）的点，根据乘法原理得到不合法的情况，注意一下 01 10 会重复计算，所以要除以二，最后从 \(n\) 个点里面找 \(3\) 个点 \(\binom{n}{3}\)，根据容斥定理减去不合法情况就是答案了。

#include <bits/stdc++.h>
#define int long long
using namespace std;

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 siz[8005];
signed 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();
            // cout<<i<<" "<<j<<" "<<edge[i][j]<<endl;
            if(!edge[i][j]) siz[i]++,siz[j]++; //white
        }
	int base = 0;
	for(int i = 0;i<n;i++) base += (n-1-siz[i])*siz[i];
	cout<<n*(n-1)*(n-2)/3/2-base/2<<endl;
 	return 0;
}