题解 | #Counting Triangles#

J - Counting Triangles

题意：
给定一张完全图，边权只有两种，问全三角形和全三角形数量。

思路：
题解好简单，我写得好麻烦QAQ。两种权值，三条边，那么对于不合法的三角形来说，会拥有两个边权不同的角，将原有答案减去不同边权角数量的一半就行了。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define dbg(x...) do{ cout << #x << " -> "; err(x);} while (0)
void err() {
    cout << endl;
}
template<class T, class ...Ts> void err(const T& arg, const Ts&... args) {
    cout << arg << " ";
    err(args...);
}

typedef long long ll;
const int maxn = 1e5 + 7;

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];
ll s[8005][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();
            s[i][edge[i][j]]++;
            s[j][edge[i][j]]++;
        }
    ll ans = (ll)n * (ll)(n - 1) * (ll)(n - 2) / 6;
    ll sub = 0;
    for (int i = 0; i < n; ++i) {
        sub += s[i][0] * s[i][1];
    }
    cout << ans - sub / 2 << endl;
    return 0;
}