#1175844 (C++23) No.3676 Cuboid Alignment

• 問題: No.3676 Cuboid Alignment
• ユーザー: 👑 みうね
• 提出日時: 2026-08-09 03:44:03
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 784 ms / 2,000 ms
• コード長: 5,723 bytes
• コンパイル時間: 1,258 ms
• コンパイル使用メモリ: 176,928 KB
• 実行使用メモリ: 26,536 KB
• 最終ジャッジ日時: 2026-09-04 22:12:54
• 合計ジャッジ時間: 16,798 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 4
other	AC * 42

ソースコード

#include <algorithm>
#include <iostream>
#include <vector>

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>

namespace cuboid_alignment {

constexpr int MOD = 998244353;

struct mint {
    int value;
    mint(long long x = 0) : value(int((x % MOD + MOD) % MOD)) {}
    mint& operator+=(const mint& rhs) {
        value += rhs.value;
        if (value >= MOD) value -= MOD;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        value -= rhs.value;
        if (value < 0) value += MOD;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        value = int((long long)value * rhs.value % MOD);
        return *this;
    }
    friend mint operator+(mint lhs, const mint& rhs) { return lhs += rhs; }
    friend mint operator-(mint lhs, const mint& rhs) { return lhs -= rhs; }
    friend mint operator*(mint lhs, const mint& rhs) { return lhs *= rhs; }
    mint pow(long long n) const {
        mint x = *this, result = 1;
        while (n > 0) {
            if (n & 1) result *= x;
            x *= x;
            n >>= 1;
        }
        return result;
    }
    mint inv() const { return pow(MOD - 2); }
};

inline void ntt(std::vector<mint>& a, bool inverse) {
    const int n = (int)a.size();
    assert(n > 0 && (n & (n - 1)) == 0);
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) std::swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        mint root = mint(3).pow((MOD - 1) / len);
        if (inverse) root = root.inv();
        for (int begin = 0; begin < n; begin += len) {
            mint w = 1;
            for (int i = 0; i < len / 2; ++i) {
                mint u = a[begin + i];
                mint v = a[begin + i + len / 2] * w;
                a[begin + i] = u + v;
                a[begin + i + len / 2] = u - v;
                w *= root;
            }
        }
    }
    if (inverse) {
        mint inv_n = mint(n).inv();
        for (mint& x : a) x *= inv_n;
    }
}

inline std::vector<mint> multidimensional_circular_convolution(
        const std::vector<mint>& a, const std::vector<mint>& b,
        const std::vector<int>& shape) {
    long long size = 1;
    for (int length : shape) { assert(length > 0); size *= length; }
    assert(size == (long long)a.size() && a.size() == b.size());

    // Embed coordinate i on each axis in radix (2 * shape[i] - 1).
    // A sum of two valid coordinates is smaller than that radix, so carries
    // never leak from one coordinate into the next coordinate.
    std::vector<int> radix(shape.size());
    long long embedded_size = 1;
    for (int i = 0; i < (int)shape.size(); ++i) {
        radix[i] = 2 * shape[i] - 1;
        embedded_size *= radix[i];
    }
    int ntt_size = 1;
    while (ntt_size < embedded_size) ntt_size <<= 1;
    assert(ntt_size <= (1 << 23));
    std::vector<mint> fa(ntt_size), fb(ntt_size);
    for (int flat = 0; flat < (int)size; ++flat) {
        int remaining = flat;
        long long embedded = 0, place = 1;
        for (int axis = 0; axis < (int)shape.size(); ++axis) {
            const int coordinate = remaining % shape[axis];
            remaining /= shape[axis];
            embedded += place * coordinate;
            place *= radix[axis];
        }
        fa[embedded] = a[flat];
        fb[embedded] = b[flat];
    }
    ntt(fa, false);
    ntt(fb, false);
    for (int i = 0; i < ntt_size; ++i) fa[i] *= fb[i];
    ntt(fa, true);

    // Fold each non-circular coordinate sum independently modulo shape[axis].
    std::vector<mint> result(size);
    for (int embedded = 0; embedded < embedded_size; ++embedded) {
        int remaining = embedded;
        int flat = 0, place = 1;
        for (int axis = 0; axis < (int)shape.size(); ++axis) {
            const int coordinate_sum = remaining % radix[axis];
            remaining /= radix[axis];
            flat += place * (coordinate_sum % shape[axis]);
            place *= shape[axis];
        }
        result[flat] += fa[embedded];
    }
    return result;
}

}  // namespace cuboid_alignment


using cuboid_alignment::mint;
using cuboid_alignment::multidimensional_circular_convolution;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int X, Y, Z;
    std::cin >> X >> Y >> Z;
    const int M = X * Y * Z;
    auto id = [=](int x, int y, int z) { return x + X * (y + Y * z); };

    std::vector<char> A(M), B(M);
    std::string row;
    for (int z = 0; z < Z; ++z)
        for (int y = 0; y < Y; ++y) {
            std::cin >> row;
            for (int x = 0; x < X; ++x) A[id(x, y, z)] = row[x];
        }
    for (int z = 0; z < Z; ++z)
        for (int y = 0; y < Y; ++y) {
            std::cin >> row;
            for (int x = 0; x < X; ++x) B[id(x, y, z)] = row[x];
        }

    std::vector<mint> A_black(M), A_white(M), B_black_rev(M), B_white_rev(M);
    for (int z = 0; z < Z; ++z) for (int y = 0; y < Y; ++y) for (int x = 0; x < X; ++x) {
        const int p = id(x, y, z);
        const int reversed = id((X - x) % X, (Y - y) % Y, (Z - z) % Z);
        A_black[p] = (A[p] == 'B');
        A_white[p] = (A[p] == 'W');
        B_black_rev[reversed] = (B[p] == 'B');
        B_white_rev[reversed] = (B[p] == 'W');
    }

    const std::vector<int> shape{X, Y, Z};
    auto black_white = multidimensional_circular_convolution(A_black, B_white_rev, shape);
    auto white_black = multidimensional_circular_convolution(A_white, B_black_rev, shape);
    int answer = M;
    for (int i = 0; i < M; ++i)
        answer = std::min(answer, black_white[i].value + white_black[i].value);
    std::cout << answer << '\n';
}