結果

問題 No.2369 Some Products
コンテスト
ユーザー hitonanode
提出日時 2023-06-30 22:54:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 237 ms / 2,500 ms
コード長 2,539 bytes
コンパイル時間 1,337 ms
コンパイル使用メモリ 105,376 KB
実行使用メモリ 86,784 KB
最終ジャッジ日時 2024-07-07 10:47:43
合計ジャッジ時間 3,038 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

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

// Disjoint sparse table
// https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404
// https://drken1215.hatenablog.com/entry/2018/09/08/162600
// Complexity: O(NlogN) for precalculation, O(1) per query
// - get(l, r): return op(x_l, ..., x_{r - 1})
template <class S, S (*op)(S, S)> struct disj_sparse_table {
    int N, sz;
    std::vector<std::vector<S>> d;
    static int _msb(int x) noexcept { return x == 0 ? 0 : (__builtin_clz(x) ^ 31); }
    disj_sparse_table() = default;
    disj_sparse_table(const std::vector<S> &seq) : N(seq.size()) {
        sz = 1 << (_msb(N - 1) + 1);
        d.assign(_msb(sz) + 1, std::vector<S>(sz));
        std::copy(seq.begin(), seq.end(), d[0].begin());

        for (int h = 1, half = 2; half < N; ++h, half <<= 1) {
            for (int i = half; i < sz; i += half * 2) {
                d[h][i - 1] = d[0][i - 1];
                for (int j = i - 2; j >= i - half; --j) d[h][j] = op(d[0][j], d[h][j + 1]);
                d[h][i] = d[0][i];
                for (int j = i + 1; j < i + half; ++j) d[h][j] = op(d[h][j - 1], d[0][j]);
            }
        }
    }
    // [l, r), 0-indexed
    S prod(int l, int r) const {
        assert(l >= 0 and r <= N and l < r);
        if (l + 1 == r) return d[0][l];
        int h = _msb(l ^ (r - 1));
        return op(d[h][l], d[h][r - 1]);
    }
};

using S = vector<mint>;
S op(S l, S r) {
    S ret(max<int>(l.size() + r.size() - 1, 0));
    REP(i, l.size()) REP(j, r.size()) ret.at(i + j) += l.at(i) * r.at(j);
    return ret;
}

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

    int N;
    cin >> N;

    vector<S> init(N);
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        init.at(i) = {1, p};
    }

    disj_sparse_table<S, op> dst(init);

    int Q;
    cin >> Q;
    while (Q--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l;

        mint ret = 0;
        if (l + 1 == r) {
            ret = dst.d[0][l][k];
        } else {
            const int h = dst._msb(l ^ (r - 1));
            REP(kl, k + 1) {
                if (kl < (int)dst.d.at(h).at(l).size() and k - kl < (int)dst.d.at(h).at(r - 1).size()) ret += dst.d.at(h).at(l).at(kl) * dst.d.at(h).at(r - 1).at(k - kl);
            }
        }
        cout << ret.val() << '\n';
    }
}
0