右辺は で計算できるので、時間計算量は問題にならないことが多いです。
使う場面
この式を使って和の和を積の和に言い換えると、分配法則が使えてやりやすくなることがあります。 ただし和の和も和の順序の交換などの良い性質を持つので、どちらが良いかは場合によります。
また、スコアと場合の数を同時に管理する DP はこの式を計算していると解釈できることがあります。 期待値と確率を同時に管理する DP も同様です。 言いかえると考察が整理しやすかったり、逆元を活用したりできます。
使用例
次のような問題を考えます。
数列に対し、そのスコアを全ての連続部分列についての「要素の和」の和と定義します。 数列
が与えられるので、
点更新クエリと区間スコア取得クエリを処理してください。
和の和なので順序の交換 (寄与を考える) をすると、 と
と
の和をセグ木で管理すればよいことが分かります。
一方で積の和に言い換えると、Do Use Segment Tree などで頻出のモノイドになります。
この場合は言い換えない方が分かりやすいかも知れません。
少し発展させて、次の問題を考えます。
頂点に数の書かれた木に対し、そのスコアを全ての連結部分グラフについての「頂点の値の和」の和と定義します。 木が与えられるので、
この問題は top tree を用いて解けますが、和の和の形のままだとどのように乗せるかはあまり明らかではありません。 一方で積の和に言い換えると、直径の管理と同じように処理できます。
関連
以下の等式を用いることで、和の 乗を積に言い換えられます。
これはモーメント母関数と同じ形です。
冒頭の式は の場合であると解釈できます。
