AT2142 [ARC062E] Building Cubes with AtCoDeer

Link

Sol

事实上确定一个立方体只需要确定上下两个面就可以了(这样子每个角的颜色就唯一确定了)

讨论一下不同情况的瓷砖

一块瓷砖有可能四个角颜色都相同,那么它随意旋转都可以对答案贡献1, 所以这种瓷砖的贡献是4

一块形似aabb的瓷砖,也就是每次旋转180\circ 颜色相同, 那么它对答案的贡献是 2

如果都不相同对答案的贡献就是 1

考虑统计答案的方式,我们每次枚举上下两个面,那么随之其他面也被确定

可以用一个哈希表,把一种瓷砖本身\旋转和全部倒过来的都存进哈希表,每次取出两个面的时候乘法原理算一下答案即可

Code

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

#define int long long

const int SIZE = 5e2 + 5;
const int key = 2002;
const int mod = 998244853;

int n, ans;
int hsh[SIZE], p[5], q[5];

std::unordered_map < int, pair < int, int > > s;

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline int getHash(int a, int b, int c, int d) {
    return a * key * key * key + b * key * key + c * key + d;
}

namespace tony102 {
    inline int swap(int x) { 
        return x % (key * key) * key * key + x / key / key;
    }

    inline int reverse(int x) {
        return x % key * key * key * key + x / key;
    }

    inline int min(int x) {
        int t = swap(x);
        return std::min(std::min(t, x), std::min(reverse(t), reverse(x)));
    }
}

inline int getVal(int x, int opt) {
    return x / q[opt] % key;
}

inline void solve(int x, int y, int tim) {
    p[1] = tony102::min(getHash(getVal(x, 1), getVal(y, 2), getVal(y, 1), getVal(x, 2)));
    if (!s[p[1]].second) return;
    p[2] = tony102::min(getHash(getVal(x, 2), getVal(y, 1), getVal(y, 4), getVal(x, 3)));
    if (!s[p[2]].second) return;
    p[3] = tony102::min(getHash(getVal(x, 3), getVal(y, 4), getVal(y, 3), getVal(x, 4)));
    if (!s[p[3]].second) return;
    p[4] = tony102::min(getHash(getVal(x, 4), getVal(y, 3), getVal(y, 2), getVal(x, 1)));
    if (!s[p[4]].second) return;
    int cnt = 1;
    for (int i = 1; i <= 4; ++ i) {
        cnt = (s[p[i]].first * s[p[i]].second) * cnt;
        -- s[p[i]].second;
    }
    for (int i = 1; i <= 4; ++ i) ++ s[p[i]].second;
    cnt = cnt * tim;
    ans = (ans + cnt);
}

signed main() {
    // freopen("intermezzo.in", "r", stdin);
    // freopen("intermezzo.out", "w", stdout);
    n = read(), q[4] = 1;
    for (int i = 3; i; -- i) q[i] = q[i + 1] * key;
    for (int i = 1, c0, c1, c2, c3; i <= n; ++ i) {
        c0 = read(), c1 = read(), c2 = read(), c3 = read();
        int h = getHash(c0, c1, c2, c3);
        h = tony102::min(h);
        if (h == tony102::reverse(h)) s[h].first = 4;
        else {
            if (h == tony102::swap(h)) s[h].first = 2;
            else s[h].first = 1;
        }
        ++ s[h].second, hsh[i] = h;
    }
    for (int i = 1; i < n - 2; ++ i) {
        -- s[hsh[i]].second;
        for (int j = i + 1; j <= n; ++ j) {
            -- s[hsh[j]].second;
            if (s[hsh[i]].first == 1) {
                solve(hsh[i], hsh[j], 1);
                solve(hsh[i], tony102::reverse(hsh[j]), 1);
                solve(hsh[i], tony102::swap(hsh[j]), 1);
                solve(hsh[i], tony102::reverse(tony102::swap(hsh[j])), 1);
            }
            else if (s[hsh[i]].first == 2) {
                solve(hsh[i], hsh[j], 2);
                solve(hsh[i], tony102::reverse(hsh[j]), 2);
            }
            else if (s[hsh[i]].first == 4) solve(hsh[i], hsh[j], 4);
            ++ s[hsh[j]].second;
        }
    }
    printf("%lld\n", ans);
    return 0;
}