#1154184 (C++23) No.3486 Draw a Rainbow

• 問題: No.3486 Draw a Rainbow
• ユーザー: Iroha_3856
• 提出日時: 2026-03-27 22:20:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,287 ms / 4,000 ms
• コード長: 3,327 bytes
• コンパイル時間: 3,794 ms
• コンパイル使用メモリ: 339,896 KB
• 実行使用メモリ: 7,716 KB
• 最終ジャッジ日時: 2026-03-27 22:21:11
• 合計ジャッジ時間: 11,717 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 28

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define ll long long
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const int inf = 1e9;
const ll INF = 4e18;

#define debug(x) cout << #x << " : " << endl; for (auto u : x) cout << u << " "; cout << endl;

std::vector<mint> xorConvolution(std::vector<mint> A, std::vector<mint> B) {
    int N = (int)A.size();
    assert((int)B.size() == N);
    assert((N&(N-1)) == 0);

    auto transform = [&N](std::vector<mint>& X) -> void {
        for (int i = 1; i < N; i <<= 1) {
            for (int j = i; j < N; j = (j + 1) | i) {
                mint s = X[j^i], t = X[j];
                X[j^i] = s + t;
                X[j] = s - t;
            }
        }
    };
    auto inverse = [&N, &transform](std::vector<mint>& X) -> void {
        transform(X);
        mint inv = mint(N).inv();
        for (mint& x : X) x *= inv;
    };
    
    transform(A); transform(B);
    for (int i = 0; i < N; i++) A[i] *= B[i];
    inverse(A);
    return A;
}

std::vector<mint> andConvolution(std::vector<mint> A, std::vector<mint> B) {
    int N = (int)A.size();
    assert((int)B.size() == N);
    assert((N&(N-1)) == 0);

    auto transform = [&N](std::vector<mint>& X) -> void {
        for (int i = 1; i < N; i <<= 1) {
            for (int j = i; j < N; j = (j + 1) | i) {
                X[j^i] += X[j];
            }
        }
    };
    auto inverse = [&N](std::vector<mint>& X) -> void {
        for (int i = 1; i < N; i <<= 1) {
            for (int j = i; j < N; j = (j + 1) | i) {
                X[j^i] -= X[j];
            }
        }
    };
    
    transform(A); transform(B);
    for (int i = 0; i < N; i++) A[i] *= B[i];
    inverse(A);
    return A;
}

std::vector<mint> orConvolution(std::vector<mint> A, std::vector<mint> B) {
    int N = (int)A.size();
    assert((int)B.size() == N);
    assert((N&(N-1)) == 0);

    auto transform = [&N](std::vector<mint>& X) -> void {
        for (int i = 1; i < N; i <<= 1) {
            for (int j = i; j < N; j = (j + 1) | i) {
                X[j] += X[j^i];
            }
        }
    };
    auto inverse = [&N](std::vector<mint>& X) -> void {
        for (int i = 1; i < N; i <<= 1) {
            for (int j = i; j < N; j = (j + 1) | i) {
                X[j] -= X[j^i];
            }
        }
    };
    
    transform(A); transform(B);
    for (int i = 0; i < N; i++) A[i] *= B[i];
    inverse(A);
    return A;
}

int main() {
    int N, M, L; cin >> N >> M >> L;

    int C[M][L];
    rep(i, 0, M) rep(j, 0, L) C[i][j] = 0;
    rep(i, 0, N) {
        int a, b; cin >> a >> b;
        a--; b--; b -= M;
        C[a][b]++;
    }

    vector<mint> dp(1 << L);
    dp[0] = 1;
    rep(i, 0, M) {
        vector<mint> ep(1 << L);
        rep(S, 1, 1 << L) {
            ep[S] = 1;
            rep(j, 0, L) {
                if (S >> j & 1) {
                    ep[S] *= (mint(2).pow(C[i][j]) - 1);
                }
            }
        }
        dp = orConvolution(dp, ep);
    }
    cout << dp.back().val() << endl;
}