コンテンツにスキップ

AALC001 G - Sum of k-th Powers

サイト
AtCoder
コンテスト
AALC001
問題
G - Sum of k-th Powers
難易度
-

長さ NN の非負整数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 l r x:Al,…,ArA_l, \dots, A_r のそれぞれに xx を足す。
  • 2 l r k:∑i=lrAik\sum_{i=l}^{r} A_i^k を 998244353998244353 で割った余りを出力する(1≤k≤41 \le k \le 4)。

遅延評価セグメント木の各ノードに、担当区間の p=0,1,…,4p = 0, 1, \dots, 4 乗和 sp=∑Aips_p = \sum A_i^p を持たせます(s0s_0 は区間の長さです)。2 つの区間の合成は、それぞれの和をとるだけです。

区間の全要素に xx を足したときは、二項定理より

∑(Ai+x)p=∑q=0p(pq)xp−q∑Aiq=∑q=0p(pq)xp−qsq\sum (A_i + x)^p = \sum_{q=0}^{p} \binom{p}{q} x^{p-q} \sum A_i^q = \sum_{q=0}^{p} \binom{p}{q} x^{p-q} s_q

となるので、新しい sps_p は古い s0,…,sps_0, \dots, s_p から計算できます。足す値の合成は和です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です(定数倍は kk の上限 44 に応じて大きくなります)。

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> は、区間加算と 00 乗から 44 乗までの和を扱う作用付きモノイドで、mapping で上の二項展開を行います。これを LazySegTree に渡しています。prod の結果に [k] を付けると kk 乗和が得られます。

使用ライブラリ:cpp_include@397a51d