AALC001 G - Sum of k-th Powers
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- G - Sum of k-th Powers
- 難易度
- -
長さ の非負整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 l r x: のそれぞれに を足す。2 l r k: を で割った余りを出力する()。
遅延評価セグメント木の各ノードに、担当区間の 乗和 を持たせます( は区間の長さです)。2 つの区間の合成は、それぞれの和をとるだけです。
区間の全要素に を足したときは、二項定理より
となるので、新しい は古い から計算できます。足す値の合成は和です。
全体の計算量は です(定数倍は の上限 に応じて大きくなります)。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/lazy-segtree.hpp"#include "shogo-library/math/modint.hpp"using mint = modint998244353;
void solve() { LL(N, Q); VL(A, N); vec<acted_monoid::AddPowerSum<mint, 4>::S> init; init.reserve(N); rep(i, N) init.emplace_back(A[i]); LazySegTree<acted_monoid::AddPowerSum<mint, 4>> seg(init); rep(Q) { LL(q); if (q == 1) { LL(l, r, x); seg.apply(l - 1, r, x); } else if (q == 2) { LL(l, r, k); print(seg.prod(l - 1, r)[k]); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}acted_monoid::AddPowerSum<mint, 4> は、区間加算と 乗から 乗までの和を扱う作用付きモノイドで、mapping で上の二項展開を行います。これを LazySegTree に渡しています。prod の結果に [k] を付けると 乗和が得られます。
使用ライブラリ:cpp_include@397a51d