ICPC 2019 模擬国内予選H: 不思議なボタン解説

問題文

問題文は以下をご覧ください。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2951&lang=jp

この記事は非公式です。この問題の公式解説は以下からご覧ください。

2019/Practice/模擬国内予選/講評 - ICPC OB/OG の会

AOJ - ICPC では難易度 800 とされています。結構難しいと思います.

2023/06/04 解説の誤植を修正しました.

解説

基本の考察

クエリの問題ですが, $e_i$ が非常に大きいです. よって, 何らかの方法で大きい $e_i$ でも高速に求められる方法を考えたいです.

また, ワープで部屋 $a$ から部屋 $b$ に飛べるときに $a$ から $b$ への有向辺があるようなグラフを作ったとき, そのグラフは DAG となります. DAG であることによって, トポロジカル順（今回はそのまま）に何らかの DP を行うことができます.

また, 冒険した部屋を $L$ 種類として, その上で「コインボタン」を押す回数が $E$ 回とします. そうすると, ボタンの押し方は多重集合の数え上げと同一で, $\binom{E+L-1}{L-1}$ 通りあります. これは $O(L)$ で求められるため, $e_i$ に依存しない解法としてこれを利用できそうです.

DPをつくる

必要な情報は「現在の部屋」, 「冒険した部屋の個数」, 「ワープボタンを押してもらったコインの枚数」です. $dp(i, j, k)$ を $i$ 番目の部屋にいるとき, いままで $j$ 個の部屋に訪ねており, そして今ワープボタンでもらったコインの個数が $k$ 個のときの通り数とします. 初期値は $dp(1, 1, 0) = 1$ です.

そうすると, グラフが DAG であることに感謝して, $a \to i$ にコイン $c$ 枚のコインボタンがある場合, $dp(i, j, k) += dp(a, j-1, k-c)$ というふうに遷移します.

これは $O(N^2 M)$ で実現できますが, $N, M \le 3000$ なので厳しいです.

ちなみにクエリに対しては, その答えは $\sum_j \sum_k dp(d_i, j, k) \times \binom{e_i -k + j-1}{j-1}$ で求められます. これも重いです.

そして形式的冪級数へ

$g_i(x, y)$ を 2 変数形式的冪級数として, $dp(i, j, k)$ が $g_i(x,y)$ の $x^j y^k$ の係数になるようなものを考えます.

本質的に遷移は変わりません. $a \to i$ にコイン $c$ 枚のコインボタンがある場合, $g_i(x, y) += g_a(x, y) \times x^c y$ というふうに遷移します.

ただし, いわゆる負の二項定理, $\binom{E+L-1}{L-1} = [x^E ] \frac{1}{(1-x)^L}$ を使うと, クエリに対する答えは $[x^{e_i} ] \sum_j ([y^j ] g_{d_i})(x) \times \frac{1}{(1-x)^j}$ と書けます

いま, $g_i$ の $y^j$ の係数（の形式的冪級数）に対しては $\frac{1}{(1-x)^j}$ が掛けられて足されますが, それをまとめることを考えます. $g_i(x,y)$ の変数 $y$ をすべて $\frac{1}{1-x}$ に置き換えたものを $f_i(x)$ とします.

そうすると, クエリに対する答えは $[x^{e_i} ] f_{d_i} (x)$ となり, シンプルになりました.

DP の遷移はどうなのでしょうか？ $y \mapsto \frac{1}{1-x}$ としたことにより, $a \to i$ にコイン $c$ 枚のコインボタンがある場合, $f_i(x) += f_a(x) \times \frac{x^c}{1-x}$ というふうに遷移します.

高速化

$\frac{1}{1-x}$ は累積和を取る操作なので, 無限項生まれてしまい困ります. $f_i(x) = \frac{h_i(x)}{(1-x)^t}$ , $h_i(x)$ は多項式, というふうに $f_i$ を管理したいです.

しかし, そうすると困るのが, 遷移が多い場合に $f_a(x)$ の分母の $(1-x)^t$ の $t$ がバラバラであると, それをすべて足し合わせるときに多項式乗算が必要になることです.

そこで, 訪れる部屋の個数は高々 $N$ 個なので, 最初から $f_i(x)$ の分母は $(1-x)^{N+1}$ に固定してしまいます. そうすると, 初期値は $f_1(x) = \frac{(1-x)^N}{(1-x)^{N+1}}$ となります. これの分子を $h_i(x)$ , すなわち $h_i(x) = f_i(x) (1-x)^{N+1}$ とします.

$a \to i$ にコイン $c$ 枚のコインボタンがある場合, $h_i(x) += h_a(x) \times \frac{x^c}{1-x}$ というふうに遷移します. $x^c$ は $c$ だけシフトすること, $\frac{1}{1-x}$ は累積和を取る操作ですが, 最初に $(1-x)^{N}$ が掛けられているのでその操作を行っても結局多項式に落ち着きます.

そして, $C$ をワープボタンでもらえるコインの最大値とすると, 1 回の遷移は計算量 $O(CN)$ に削減されています. というのも, $h_i(x)$ の次数は遷移ごとに $C=3$ までしか増えないので, 次数は $(C+1) N$ で抑えられるからです. そして, 遷移は「累積和をとり, シフトして足す」だけなので軽いものとなっています.

クエリに対しては, $[x^{e_i} ] h_{d_i} (x) \frac{1}{(1-x)^{N+1}}$ を求めればいいのですが, $h_{d_i}(x)$ の多項式の次数を $L$ とすればこれは $\sum_{k=0}^{L} ([x^k ] h_{d_i} (x)) \binom{e_i+L-k+N}{N}$ を求めればよいことになります.

$\binom{e_i+L-k+N}{N}$ を $k=0, 1, \cdots, L$ について求めることは, 逐次的に計算していけば $O(L)$ で達成できます. これはたとえば SWAG と呼ばれるアルゴリズムでできます. また, TL が厳しく, $O(L \log P)$ では TLE が出るのが悲しいです.