cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: Static range product query with precalculation （前計算埋め込み）
(utilities/product_embedding.hpp)

$\bmod$ 階乗などの計算を前計算して埋め込み， ${}_n \mathrm{P}_r$ などのクエリに高速で結果を返す．

できること

（結合法則を満たす）乗法が定義された要素の列 $f(0), f(1), \dots$ を考える．$f(i)$ たちの値は陽には持たないが，$i$ の値を与えると $f(i)$ は十分高速に求められるものとする．バケットサイズとして正の整数 $B$ を定める．$F(k) = f(Bk) f(Bk + 1) \cdots f((B + 1)k - 1)$ の値を各 $k$ について前計算しておけば，任意のクエリ $(l, r)$ について $f(l) f(l + 1) \cdots f(r - 1)$ の値が $O(B + (r - l) / B)$ で求まる．

本コードは前計算した $F(k)$ の値の一覧をテキストファイルに出力する機能，およびこの前計算された結果を元に $f(l) \cdots f(r - 1)$ の値を計算するメソッドを提供する．

使用方法

「問題例」に挙げた階乗クエリを高速に処理したいケースで述べる．

まず前計算として，以下のようなコードを書いてコンパイルし実行する．

using S = int;
constexpr S md = 1000000007;
S op(S l, S r) { return (long long)l * r % md; }
S e() { return 1; }
S getter(long long i) { return i + 1 >= md ? (i + 1) % md : i + 1; }  // f(i) = i + 1
using PE = product_embedding<S, op, e, getter, 500000>;

int main() {
    PE::prerun("tmp.txt", len);  // 0 <= l <= r <= len までのクエリ (l, r) の実行を保証する．
}

すると，tmp.txt というテキストファイルが生成されるので，その中身を用いて改めて PE クラスのインスタンスを生成し，これを用いて問題を解く．

int main() {
    PE pe({154425679,765215884,239137314, ..., 899058414,0}); // 「PE pe」以降は tmp.txt のコピペで OK

    int ret = pe.prod(l, r);  // f(l) * ... * f(r - 1) = (l + 1) * ... * r の計算結果
}

問題例

Verified with

Code

#pragma once
#include <cassert>
#include <fstream>
#include <vector>

// 結合法則が成立する要素の列について連続部分列の積を前計算を利用し高速に求める
template <class S, S (*op)(S, S), S (*e)(), S (*getter)(long long), int Bucket>
struct product_embedding {
    std::vector<S> pre_; // pre_[i] = S[i * Bucket] * ... * S[(i + 1) * Bucket - 1]

    product_embedding(std::vector<S> pre) : pre_(pre) {}

    S prod(long long l, long long r) { // S[l] * ... * S[r - 1]
        assert(0 <= l);
        assert(l <= r);
        assert(r <= (long long)Bucket * (long long)pre_.size());

        if (r - l <= Bucket) {
            S ret = e();
            while (l < r) ret = op(ret, getter(l++));
            return ret;
        }

        long long lb = (l + Bucket - 1) / Bucket, rb = r / Bucket;
        S ret = e();
        for (long long i = l; i < lb * Bucket; ++i) ret = op(ret, getter(i));
        for (int i = lb; i < rb; ++i) ret = op(ret, pre_[i]);
        for (long long i = rb * Bucket; i < r; ++i) ret = op(ret, getter(i));
        return ret;
    }

    static void prerun(std::string filename, long long upper_lim) {
        std::ofstream ofs(filename);

        long long cur = 0;
        long long num_bucket = (upper_lim + Bucket - 1) / Bucket;

        ofs << "({";
        while (num_bucket--) {
            S p = e();
            for (int t = 0; t < Bucket; ++t) { p = op(p, getter(cur++)); }
            ofs << p;
            if (num_bucket) ofs << ",";
        }
        ofs << "});";
    }
};
/* Usage:
using S = int;
constexpr S md = 1000000007;
S op(S l, S r) { return (long long)l * r % md; }
S e() { return 1; }
S getter(long long i) { return i + 1 >= md ? (i + 1) % md : i + 1; }
using PE = product_embedding<S, op, e, getter, 500000>;

int main() {
    PE::prerun("tmp.txt", md);  // -> copy & paste the content of dumped file
}
*/
#line 2 "utilities/product_embedding.hpp"
#include <cassert>
#include <fstream>
#include <vector>

// 結合法則が成立する要素の列について連続部分列の積を前計算を利用し高速に求める
template <class S, S (*op)(S, S), S (*e)(), S (*getter)(long long), int Bucket>
struct product_embedding {
    std::vector<S> pre_; // pre_[i] = S[i * Bucket] * ... * S[(i + 1) * Bucket - 1]

    product_embedding(std::vector<S> pre) : pre_(pre) {}

    S prod(long long l, long long r) { // S[l] * ... * S[r - 1]
        assert(0 <= l);
        assert(l <= r);
        assert(r <= (long long)Bucket * (long long)pre_.size());

        if (r - l <= Bucket) {
            S ret = e();
            while (l < r) ret = op(ret, getter(l++));
            return ret;
        }

        long long lb = (l + Bucket - 1) / Bucket, rb = r / Bucket;
        S ret = e();
        for (long long i = l; i < lb * Bucket; ++i) ret = op(ret, getter(i));
        for (int i = lb; i < rb; ++i) ret = op(ret, pre_[i]);
        for (long long i = rb * Bucket; i < r; ++i) ret = op(ret, getter(i));
        return ret;
    }

    static void prerun(std::string filename, long long upper_lim) {
        std::ofstream ofs(filename);

        long long cur = 0;
        long long num_bucket = (upper_lim + Bucket - 1) / Bucket;

        ofs << "({";
        while (num_bucket--) {
            S p = e();
            for (int t = 0; t < Bucket; ++t) { p = op(p, getter(cur++)); }
            ofs << p;
            if (num_bucket) ofs << ",";
        }
        ofs << "});";
    }
};
/* Usage:
using S = int;
constexpr S md = 1000000007;
S op(S l, S r) { return (long long)l * r % md; }
S e() { return 1; }
S getter(long long i) { return i + 1 >= md ? (i + 1) % md : i + 1; }
using PE = product_embedding<S, op, e, getter, 500000>;

int main() {
    PE::prerun("tmp.txt", md);  // -> copy & paste the content of dumped file
}
*/
Back to top page