https://codeforces.com/gym/103470/problem/K

第三次发帖问了，上次被提醒用哈希实现边与其编号的转化，嗯，效果显著： $\tt TLE\ on\ test\ 28\rightarrow\ TLE\ on\ test\ 38$

好累哦，又菜了一天.jpg 求卡常或指出实现丑拉复杂度的情况。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
const int N = 2e5 + 10, mod = 19260817, B = 2e7; typedef long long ll;
inline int getHash(const int& x, const int& y) { return ((ll)x * N + y) % mod; }
std::vector<int> E[N], G[N]; int a[N], b[N], deg[N]; ll f[10];
inline ll Cn4(const int& n)
{
    ll div[3] = {4, 3, 2}, cnt[3] = {}, a[4] = {n, n - 1, n - 2, n - 3};
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 3; ++j)
            if (a[i] % div[j] == 0 && !cnt[j]) a[i] /= div[j], cnt[j] = 1;
    return a[0] * a[1] * a[2] * a[3];
}
int vis[N], cnt[N], d[N]; std::pair<int, int> id[N]; int book[B];
inline void read(int& x)
{
    x = 0; char ch; int f = 1;
    while ((ch = getchar()) < '0' || ch > '9') f = (ch == '-' ? -1 : 1);
    while (x = (x << 1) + (x << 3) + ch - '0', ((ch = getchar()) >= '0' && ch <= '9')) ;
    x *= f;
}
int main()
{
    int n, m; read(n); read(m);
    for (int i = 1; i <= m; ++i)
    {
        read(a[i]); read(b[i]); ++deg[a[i]], ++deg[b[i]];
        book[getHash(a[i], b[i])] = book[getHash(b[i], a[i])] = i;
    }
    for (int i = 1; i <= n; ++i) id[i] = std::make_pair(deg[i], i);
    for (int i = 1; i <= m; ++i)
    {
        E[a[i]].push_back(b[i]); E[b[i]].push_back(a[i]);
        if (id[a[i]] < id[b[i]]) G[a[i]].push_back(b[i]);
        else G[b[i]].push_back(a[i]);
    }
    // f_0 一个都不钦定，直接 \binom{n}{4} 随便选 4 个
    // f_1 钦定一个，这样会确定 2 个点，剩下的 2 个点随便，即 m\binom{n-2}{2}
    f[0] = Cn4(n); f[1] = (ll)(n - 2) * (n - 3) / 2 * m;
    // f_2 钦定两个 2 个，分两种情况，一种是两条边在同一点上，这时候用度数做就好了
    // 确定了 3 个点，剩下的 1 个点随便，即 \sum \binom{deg_i}{2}\binom{n-3}{1}
    // 然后是两边没有关系，此时每条边可选择的范围为除了与边的两点直接相连的边和自己
    // 即 m - deg_{a_i} - deg_{b_i} + 1，确定了 4 个点，但注意这会算重，所以要除 2
    for (int i = 1; i <= m; ++i) f[2] += (m - deg[a[i]] - deg[b[i]] + 1);
    f[2] /= 2;
    for (int i = 1; i <= n; ++i)
    {
        if (deg[i] <= 1) continue;
        f[2] += (ll)deg[i] * (deg[i] - 1) / 2 * (n - 3);
    }
    int ret = 0;
    for (int u = 1; u <= n; ++u)
    {
        for (auto v : G[u]) vis[v] = u; 
        for (auto v : G[u]) for (auto w : G[v]) 
            if (vis[w] == u) 
            {
                f[4] += std::max(0, deg[u] - 2) + std::max(0, deg[v] - 2) + std::max(0, deg[w] - 2);
                ++cnt[book[getHash(u, v)]];
                ++cnt[book[getHash(v, w)]];
                ++cnt[book[getHash(w, u)]];
                ++ret;
            }
    }
    // f_3 钦定三个，分 3 种情况，首先是一个三元环，这确定了 3 个点，
    // 剩下的随便选，即 cnt3\binom{n-3}{1}
    // 然后是三个点全在一个点上，此时就是找与该点所有相连的点中 3 个，
    // 确定了 4 个点，即 \sum \binom{deg_i}{3}
    // 最后是三条边构成一条链，此时找链中间那条边，枚举边的两端点的出边，
    // 确定了 4 个点，即 \sum (deg_{a_i}-1)(deg_{a_i}-1)
    // 但这样会把每个三元环多算 3 次，要减去
    f[3] += (ll)ret * (n - 3);
    for (int i = 1; i <= m; ++i) f[3] += (ll)(deg[a[i]] - 1) * (deg[b[i]] - 1);
    f[3] -= ret * 3ll;
    for (int i = 1; i <= n; ++i)
    {
        if (deg[i] <= 2) continue;
        f[3] += (ll)deg[i] * (deg[i] - 1) / 2 * (deg[i] - 2) / 3;
    }
    // f_4 钦定四个，分 2 种情况，首先是一个四元环，没什么好说的，
    // 确定 4 个点，即 cnt4
    // 然后是一个三元环带一个出边，枚举所有三元环，然后检查出边即可，
    // 确定 4 个点，即 \sum ((deg_u-2)+(deg_v-2)+(deg_w-2))
    for (int u = 1; u <= n; ++u)
    {
        for (auto v : E[u]) for (auto w : G[v])
            if (id[w] > id[u]) f[4] += d[w]++;
        for (auto v : E[u]) for (auto w : G[v])
            if (id[w] > id[u]) d[w] = 0;
    }
    // f_5 钦定 5 个，只能是两个三元环拼起来，枚举那个被两个三元环都包含的边即可，
    // 确定 4 个点，即 \sum \binom{cnt_i}{2}
    for (int i = 1; i <= m; ++i) 
    {
        if (cnt[i] <= 1) continue;
        f[5] += (ll)cnt[i] * (cnt[i] - 1) / 2;
    }
    ll ans = 0;
    for (int i = 0; i < 6; ++i) if (i & 1) ans -= f[i]; else ans += f[i];
    printf("%lld\n", std::abs(ans)); return 0;
}