#982474 (C++23) No.2762 Counting and Deleting

提出ソース

結果

問題	No.2762 Counting and Deleting
ユーザー	rniya
提出日時	2024-05-17 23:03:33
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	180 ms / 4,000 ms
コード長	7,891 bytes
コンパイル時間	2,872 ms
コンパイル使用メモリ	262,492 KB
実行使用メモリ	12,912 KB
最終ジャッジ日時	2024-05-17 23:03:41
合計ジャッジ時間	5,155 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	139 ms 12,684 KB
testcase_08	AC	142 ms 12,792 KB
testcase_09	AC	141 ms 12,872 KB
testcase_10	AC	138 ms 12,796 KB
testcase_11	AC	180 ms 12,812 KB
testcase_12	AC	156 ms 12,844 KB
testcase_13	AC	157 ms 12,812 KB
testcase_14	AC	156 ms 12,864 KB
testcase_15	AC	110 ms 12,792 KB
testcase_16	AC	112 ms 12,912 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

#include <atcoder/modint>
#include <atcoder/segtree>

template <typename T, size_t N> struct SquareMatrix {
    std::array<std::array<T, N>, N> A;

    SquareMatrix() : A{{}} {}

    size_t size() const { return N; }

    inline const std::array<T, N>& operator[](int k) const { return A[k]; }

    inline std::array<T, N>& operator[](int k) { return A[k]; }

    static SquareMatrix I() {
        SquareMatrix res;
        for (size_t i = 0; i < N; i++) res[i][i] = 1;
        return res;
    }

    SquareMatrix& operator+=(const SquareMatrix& B) {
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                (*this)[i][j] += B[i][j];
            }
        }
        return *this;
    }

    SquareMatrix& operator-=(const SquareMatrix& B) {
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                (*this)[i][j] -= B[i][j];
            }
        }
        return *this;
    }

    SquareMatrix& operator*=(const SquareMatrix& B) {
        std::array<std::array<T, N>, N> C = {};
        for (size_t i = 0; i < N; i++) {
            for (size_t k = 0; k < N; k++) {
                for (size_t j = 0; j < N; j++) {
                    C[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        A.swap(C);
        return *this;
    }

    SquareMatrix& operator*=(const T& v) {
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                (*this)[i][j] *= v;
            }
        }
        return *this;
    }

    SquareMatrix& operator/=(const T& v) {
        T inv = T(1) / v;
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                (*this)[i][j] *= inv;
            }
        }
        return *this;
    }

    SquareMatrix& operator^=(long long k) {
        assert(0 <= k);
        SquareMatrix B = SquareMatrix::I();
        while (k > 0) {
            if (k & 1) B *= *this;
            *this *= *this;
            k >>= 1;
        }
        A.swap(B.A);
        return *this;
    }

    SquareMatrix operator-() const {
        SquareMatrix res;
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                res[i][j] = -(*this)[i][j];
            }
        }
        return res;
    }

    SquareMatrix operator+(const SquareMatrix& B) const { return SquareMatrix(*this) += B; }

    SquareMatrix operator-(const SquareMatrix& B) const { return SquareMatrix(*this) -= B; }

    SquareMatrix operator*(const SquareMatrix& B) const { return SquareMatrix(*this) *= B; }

    SquareMatrix operator*(const T& v) const { return SquareMatrix(*this) *= v; }

    SquareMatrix operator/(const T& v) const { return SquareMatrix(*this) /= v; }

    SquareMatrix operator^(const long long k) const { return SquareMatrix(*this) ^= k; }

    bool operator==(const SquareMatrix& B) const { return A == B.A; }

    bool operator!=(const SquareMatrix& B) const { return A != B.A; }

    SquareMatrix transpose() const {
        SquareMatrix res;
        for (size_t i = 0; i < N; i++) {
            for (size_t j = 0; j < N; j++) {
                res[j][i] = (*this)[i][j];
            }
        }
        return res;
    }

    T determinant() const {
        SquareMatrix B(*this);
        T res = 1;
        for (size_t i = 0; i < N; i++) {
            int pivot = -1;
            for (size_t j = i; j < N; j++) {
                if (B[j][i] != 0) {
                    pivot = j;
                    break;
                }
            }
            if (pivot == -1) return 0;
            if (pivot != (int)i) {
                res *= -1;
                std::swap(B[i], B[pivot]);
            }
            res *= B[i][i];
            T inv = T(1) / B[i][i];
            for (size_t j = 0; j < N; j++) B[i][j] *= inv;
            for (size_t j = i + 1; j < N; j++) {
                T a = B[j][i];
                for (size_t k = 0; k < N; k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
    }

    SquareMatrix inv() const {
        SquareMatrix B(*this), C = SquareMatrix::I();
        for (size_t i = 0; i < N; i++) {
            int pivot = -1;
            for (size_t j = i; j < N; j++) {
                if (B[j][i] != 0) {
                    pivot = j;
                    break;
                }
            }
            if (pivot == -1) return {};
            if (pivot != (int)i) {
                std::swap(B[i], B[pivot]);
                std::swap(C[i], C[pivot]);
            }
            T inv = T(1) / B[i][i];
            for (size_t j = 0; j < N; j++) {
                B[i][j] *= inv;
                C[i][j] *= inv;
            }
            for (size_t j = 0; j < N; j++) {
                if (j == i) continue;
                T a = B[j][i];
                for (size_t k = 0; k < N; k++) {
                    B[j][k] -= B[i][k] * a;
                    C[j][k] -= C[i][k] * a;
                }
            }
        }
        return C;
    }

    friend std::ostream& operator<<(std::ostream& os, const SquareMatrix& p) {
        os << "[(" << N << " * " << N << " Matrix)";
        os << "\n[columun sums: ";
        for (size_t j = 0; j < N; j++) {
            T sum = 0;
            for (size_t i = 0; i < N; i++) sum += p[i][j];
            ;
            os << sum << (j + 1 < N ? "," : "");
        }
        os << "]";
        for (size_t i = 0; i < N; i++) {
            os << "\n[";
            for (size_t j = 0; j < N; j++) os << p[i][j] << (j + 1 < N ? "," : "");
            os << "]";
        }
        os << "]\n";
        return os;
    }
};

using ll = long long;

using namespace std;

using mint = atcoder::modint998244353;
constexpr int SIZE = 2;
using SM = SquareMatrix<mint, SIZE + 1>;  // 末尾が i の整数の個数

SM op(SM l, SM r) { return r * l; }

SM e() { return SM::I(); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    vector<SM> init;
    for (int i = 0; i < N; i++) {
        int x = S[i] - '0';
        auto m = SM::I();
        for (int j = 0; j < SIZE + (x != 0); j++) m[x][j] = 1;
        init.emplace_back(m);
    }
    atcoder::segtree<SM, op, e> seg(init);
    set<int> alive;
    for (int i = 0; i < N; i++) alive.emplace(i);

    for (; Q--;) {
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        if (t == 1) {
            for (auto itr = alive.lower_bound(l); itr != alive.end() and *itr < r; itr = alive.erase(itr)) {
                seg.set(*itr, SM::I());
            }
        } else {
            auto res = seg.prod(l, r);
            mint ans = 0;
            for (int j = 0; j < SIZE; j++) ans += res[j][SIZE];
            cout << ans.val() << '\n';
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード