ABC399-F Range Power Sum が， 積の和典型だとのことなので，関連記事へのリンクなど．

リンク

ABC399-F

問題概要

問題へのリンク

$A = (A_1, \dots, A_N)$ が与えられる．次を mod 998244353 で求めよ:

$$ \sum_{1 \leq l \leq r \leq N}\left( \sum_{l \leq i \leq r} A_i \right)^K $$

制約: $N \leq 2\times 10^5$, $K \leq 10$．

解法

(累積和で2項展開しても解けるが，それは置いといて…) 以下， 公式解説 より．

次のように言い換えられる．

  • ボールが $A_i$ 個入った箱が一列に並んでいる．
  • 箱の間に，2個の仕切りを入れる．
  • 2つの仕切りの間にあるボールに，$1, 2, \ldots, K$ と書かれたラベルを1枚ずつ貼る

仕切りの入れ方とラベルの貼り方をセットで考えて，この方法の数が，求める答になる． DP で求める．

dp[i][j][k] = (箱 i まで見て，仕切りを j 個入れていて，ラベルを k 枚貼るような方法の数)