公式

N - 有限べき級数/Finite Power Series 解説 by MMNMM

\(\displaystyle\sum _ {i=0} ^ {r - l}A _ {i+l}x ^ i\) は、\(0\) に対して一次関数 \(f _ i:t\mapsto xt+A _ i\) を \(f _ r, f _ {r-1},\ldots,f _ l\) の順に適用したもの \((f _ l\circ f _ {l+1}\circ\cdots\circ f _ r)(0)\) と考えることができます。

余談

\(\mathbb R\) の値を正確に管理することができる場合、\(\mathbb R\to\mathbb R\) の関数 \(f _ i\) はつねに逆関数をもつため \((f _ 1\circ f _ 2\circ\cdots\circ f _ i)(0)\ (1\leq i\leq N)\) の値をすべて求めておくことでこの問題に答えることができます（\(1\) 次の係数 \(x ^ i\) を求めるのはすぐにできます）。

しかし、浮動小数点数で計算を行う場合、\(f _ 1\circ\dotsb\circ f _ i\) の逆関数が存在しない（引数の影響が十分小さくなり、\(1\) 次の係数を浮動小数点数で表すと \(0\) になってしまう）場合があります。 そのため、先頭からの累積和を用いてこの問題を解くのは難しいです。

一次関数とその合成をセグメント木や Disjoint Sparse Table に乗せて管理することを考えます。 係数を浮動小数点数で管理する場合、これはモノイドになりませんが、今回の制約のもとで実数係数のモノイドを十分な精度で近似することができます。

浮動小数点数の組 \((a,b)\) を一次関数 \(f _ {a,b}:t\mapsto a+bt\) に対応させると、合成 \(f _ {a,b}\circ f _ {c,d}=f _ {a+bc,bd}\) と恒等関数 \(f _ {0,1}\) に対応した演算 \((a,b)\cdot(c,d)=(a+bc,bd)\) と単位元 \((0,1)\) を管理すればよいです。

実装例は以下のようになります。

#include <utility>
#include <iostream>
#include <vector>
#include <ranges>
#include <iomanip>
#include <atcoder/segtree>

int main() {
    // セグメント木の準備
    // 区間 [l, r) に対応する値は 2 つ組 (A[l] + A[l+1]x + ... + A[r-1]x^(l-r+1), x^(l-r))
    // 区間の合併は (a, b) * (c, d) = (a + b * c, b * d)
    // 単位元は (0, 1)
    using value_type = std::pair<double, double>;
    using segment_tree = atcoder::segtree<value_type, [](const value_type &lhs, const value_type &rhs) {
        const auto &[lvalue, lcoef]{lhs};
        const auto &[rvalue, rcoef]{rhs};
        return value_type{lvalue + lcoef * rvalue, lcoef * rcoef};
    }, [] { return value_type{0, 1}; }>;

    unsigned N;
    std::cin >> N;
    std::vector<unsigned> A(N);
    for (auto &&a: A)
        std::cin >> a;
    double x;
    std::cin >> x;

    // A[i] -> (A[i], x) に変換してそこからセグメント木を作る
    segment_tree segtree([](auto &&a) { return std::vector(begin(a), end(a)); }(A | std::views::transform([&x](auto &&a) { return value_type{a, x}; })));

    // 適切な精度で出力
    std::cout << std::fixed << std::setprecision(10);

    unsigned Q;
    std::cin >> Q;
    for (unsigned i{}, l, r; i < Q; ++i) {
        std::cin >> l >> r;
        std::cout << segtree.prod(l - 1, r).first << std::endl;
    }
    return 0;
}

投稿日時:
最終更新: