提出 #73343960

---

ソースコード 拡げる

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
// #include<sys/time.h>
// #include<atcoder/segtree>
// #include<atcoder/modint>

using namespace std;

// using mint = atcoder::modint998244353;

using P = pair<int, int>;
const int M = 998244353;
const long long LM = 1LL << 60;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    for (int _ = 0; _ < T; ++_) {
        int n, m;
        long long d;
        cin >> n >> m >> d;
        vector<vector<long long>> a(n, vector<long long>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> a[i][j];
            }
        }
        auto check = [&](int i, int j) {
            long long s = 0;
            for (int k = 0; k < m; ++k) {
                s += abs(a[i][k] - a[j][k]);
            }
            return s <= d;
        };

        vector<int> v;
        for (int k = 0; k < (1 << m); ++k) {
            int bi = -1;
            long long ma = -LM;
            for (int i = 0; i < n; ++i) {
                long long s = 0;
                for (int j = 0; j < m; ++j) {
                    if ((k >> j) & 1) {
                        s -= a[i][j];
                    }
                    else {
                        s += a[i][j];
                    }
                }
                if (ma < s) {
                    ma = s;
                    bi = i;
                }
            }
            v.push_back(bi);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int l = v.size();
        vector<bool> in_v(n);
        for (auto&& i : v) {
            in_v[i] = true;
        }
        long long ans = 1;
        vector<vector<int>> adj(l, vector<int>(l, -1));
        for (int i = 0; i < l; ++i) {
            adj[i][i] = 0;
            for (int j = i + 1; j < l; ++j) {
                if (!check(v[i], v[j])) {
                    adj[i][j] = adj[j][i] = 1;
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            if (in_v[i]) {
                continue;
            }
            vector<int> w;
            for (int j = 0; j < (int)v.size(); ++j) {
                if (!check(i, v[j])) {
                    w.push_back(j);
                }
            }
            if (w.empty()) {
                ans = ans * 2 % M;
            }
            for (int j = 0; j < (int)w.size(); ++j) {
                for (int k = j + 1; k < (int)w.size(); ++k) {
                    if (adj[w[j]][w[k]] == 1) {
                        ans = 0;
                        break;
                    }
                    adj[w[j]][w[k]] = adj[w[k]][w[j]] = 0;
                }
            }
        }
        if (ans == 0) {
            cout << ans << '\n';
            continue;
        }
        vector<int> col(l, -1);
        for (int i = 0; i < l; ++i) {
            if (col[i] != -1) {
                continue;
            }
            ans = ans * 2 % M;
            queue<int> q;
            col[i] = 0;
            q.push(i);
            while (!q.empty()) {
                auto p = q.front();
                q.pop();
                for (int j = 0; j < l; ++j) {
                    if (adj[p][j] == -1) {
                        continue;
                    }
                    if (col[j] == -1) {
                        col[j] = col[p] ^ adj[p][j];
                        q.push(j);
                    }
                    else if (col[j] != (col[p] ^ adj[p][j])) {
                        ans = 0;
                        break;
                    }
                }
            }
            if (ans == 0) {
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果