Suuさんのブログ

Count Subset Sum

はじめに

Library Checker さんの $\# _ p$ Subset Sum

Library Checker

を解いたのですが, 日本語の解説がぱっと見なさそう？なので書いておきます

(タイトルに数式を入れる方法がわからなかったので Count Subset Sum としましたやり方知ってる方がいたら教えてください)

本文

概要

整数列 $s_0, s_1, \cdots, s_{n-1}$ があったときに, 各 $t \in [1, T$ ] について, 総和が $t$ になるような部分列の数を $\bmod 998244353$ で求めます

制約

$1\le n \le 10 ^ 6$
$1 \le T \le 5\times10 ^ 5$
$1 \le s_i \le T$

解法

みんな大好き形式的冪級数で考えます

$s_i$ を使う/使わないを $1 + x ^ {s_i}$ と表現すれば

$f(x) = \displaystyle\prod_{i = 0}^{n-1} (1 + x^{s_i})$ としたときに $f(x)$ の $x ^ t$ の項の係数が $t$ に対する答えです

さて, これは次数がとても大きくなりうるので高速に計算するのはつらいです

ということで, 積を計算するのはつらいので和に変換します

$f(x) = \exp(\log f(x)) = \exp( \displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i}) )$

形式的冪級数の $\exp$ はニュートン法を用いることで項数を $n$ として $O(n\log n)$ で求めることができるので, $\displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i})$ を求めることができれば $O(T\log T)$ で答えが求まります

ということで $\displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i})$ を求めます

ここで, $\log (1 + x)$ のマクローリン展開を考えると

$\log (1 + x) = x - \dfrac{x ^ 2}{2} + \dfrac{x ^ 3}{3} - \cdots = \displaystyle\sum _ {k \ge 1}\dfrac{(-1) ^ {k-1}}{k} x ^ k$

と書けるので,

$\log (1 + x ^ {s_i}) = \displaystyle\sum _ {k \ge 1}\dfrac{(-1) ^ {k-1}}{k} x ^ {k{s_i}}$

です無限に続きますが, 今回次数は $T$ あれば十分です

さて, $c_k$ を $s_i = k$ となるような $i$ の数とすると

$\displaystyle\sum _ {i = 0} ^ {n-1} \log (1 + x ^ {s_i}) = \displaystyle\sum _ {k = 1} ^ {T} c_k \log (1 + x ^ {k})$

と書けますが, 各 $k$ について上の式を計算すると計算回数は調和級数で抑えられます

ということでこちらは $O(n + T\log T)$ で求めることができます

全体でみても $O(n + T\log T)$ で求めることができました

おわりに

【競技プログラミング】形式的冪級数の応用テクニック(前編) - Qiita

https://arxiv.org/pdf/1807.11597.pdf

この辺見たらわかると思います