結果

問題 No.1958 Bit Game
ユーザー nonon
提出日時 2025-08-14 20:37:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 100 ms / 2,000 ms
コード長 5,385 bytes
コンパイル時間 3,783 ms
コンパイル使用メモリ 292,544 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-08-14 20:37:19
合計ジャッジ時間 9,232 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }

#include <atcoder/modint>
using mint = atcoder::modint998244353;

template<typename mint>
struct matrix : vector<vector<mint>> {
    using vector<vector<mint>>::vector;
    matrix(int h, int w) : vector<vector<mint>>(h, vector<mint>(w)) {}
    matrix &operator*=(const mint &r) {
        for (vector<mint> &v : *this) {
            for (mint &a : v) a *= r;
        }
        return *this;
    }
    matrix &operator/=(const mint &r) {
        mint invr = r.inv();
        return *this *= invr;
    }
    matrix &operator+=(const matrix& a) {
        assert(this->size() == a.size());
        for (int i = 0; i < int(this->size()); i++) {
            assert((*this)[i].size() == a[i].size());
            for (int j = 0; j < int((*this)[i].size()); j++) {
                (*this)[i][j] += a[i][j];
            }
        }
        return *this;
    }
    matrix &operator-=(const matrix& a) {
        assert(this->size() == a.size());
        for (int i = 0; i < int(this->size()); i++) {
            assert((*this)[i].size() == a[i].size());
            for (int j = 0; j < int((*this)[i].size()); j++) {
                (*this)[i][j] -= a[i][j];
            }
        }
        return *this;
    }
    matrix &operator*=(const matrix &a) {
        int n = this->size(), m = a.size();
        assert(m >= 1);
        int l = a[0].size();
        matrix res(n, vector<mint>(l));
        for (int i = 0; i < n; i++) {
            assert(int((*this)[i].size()) == m);
            for (int k = 0; k < m; k++) {
                for (int j = 0; j < l; j++) {
                    res[i][j] += (*this)[i][k] * a[k][j];
                }
            }
        }
        return *this = res;
    }
    matrix operator*(const mint &r) const { return matrix(*this) *= r; }
    matrix operator/(const mint &r) const { return matrix(*this) /= r; }
    matrix operator+(const matrix &a) const { return matrix(*this) += a; }
    matrix operator-(const matrix &a) const { return matrix(*this) -= a; }
    matrix operator*(const matrix &a) const { return matrix(*this) *= a; }
    static constexpr matrix I(int n) {
        matrix res(n, n);
        for (int i = 0; i < n; i++) {
            res[i][i] = 1;
        }
        return res;
    }
    static constexpr matrix O(int n) { return matrix(n, n); }
    matrix pow(long long k) const {
        matrix res = I(this->size()), a = *this;
        while (k > 0) {
            if (k & 1) res *= a;
            a *= a;
            k >>= 1;
        }
        return res;
    }
    mint det() const {
        int n = this->size();
        assert(n >= 1);
        assert((*this)[0].size() == this->size());
        mint res = 1;
        matrix a = *this;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (a[j][i] != 0) {
                    if (i != j) res = -res;
                    swap(a[i], a[j]);
                    break;
                }
            }
            if (a[i][i] != 0) {
                for (int j = i + 1; j < n; j++) {
                    mint inv = a[j][i] * a[i][i].inv();
                    for (int k = i + 1; k < n; k++) {
                        a[j][k] -= a[i][k] * inv;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            res *= a[i][i];
        }
        return res;
    }
    matrix inv() const {
        int n = this->size();
        matrix a = *this, res = I(n);
        for (int i = 0; i < n; i++) {
            if (a[i][i] == 0) {
                for (int j = i + 1; j < n; j++) {
                    if (a[j][i] != 0) {
                        swap(a[i], a[j]);
                        swap(res[i], res[j]);
                        break;
                    }
                }
            }
            assert(a[i][i] != 0);
            mint cef = a[i][i].inv();
            for (int j = 0; j < n; j++) {
                a[i][j] *= cef;
                res[i][j] *= cef;
            }
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    cef = a[j][i];
                    for (int k = 0; k < n; k++) {
                        a[j][k] -= a[i][k] * cef;
                        res[j][k] -= res[i][k] * cef;
                    }
                }
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(X), B(Y);
    for (auto &e : A) cin >> e;
    for (auto &e : B) cin >> e;
    auto f = [&] (mint a0, mint a1, mint b0, mint b1) -> mint {
        matrix<mint> M = matrix<mint>::I(2);
        M *= matrix<mint>{
            {1, 0},
            {a1 / X, a0 / X}
        };
        M *= matrix<mint>{
            {b1 / Y, b0 / Y},
            {0, 1}
        };
        M = M.pow(N);
        return M[1][0];
    };
    mint ans = 0;
    for (int i = 0; i < 18; i++) {
        int a0 = 0, a1 = 0, b0 = 0, b1 = 0;
        for (int a : A) (a >> i & 1 ? a1 : a0)++;
        for (int b : B) (b >> i & 1 ? b1 : b0)++;
        ans += (1 << i) * f(a0, a1, b0, b1);
    }
    ans *= (mint(X) * mint(Y)).pow(N);
    cout << ans.val() << endl;
}
0