FPS24 G - 硬貨

考え方

無制限ナップサック問題、というか無制限部分和問題。
$1$ つ答えるだけなら、ABCで言うD問題レベルで、普通に動的計画法で $O(LN)$ で解ける。

問題は、同じような問題を多数解かなくてはいけないところ。
$M-L+1$ 個を毎回求めていると、$O((M-L+1)LN)$ で間に合わない。

そこで、$m=1$ のときのナップサック問題の解法を改めて見つめなおしてみる。

• まず最初に、合計 $0$ のときだけ $1$ パターンという状態からスタートする
• そこに $1$ を好きな回数足していいとすると、全ての値に対するパターン数が $1$ になる
• さらに $2$ も好きな回数足していいとすると、同じ数が $2$ 回ずつ並ぶ数列になる

さて、これについて形式的冪級数の目線から見てみよう。
よく考えるとこれは、以下の計算と実は全く同じことをしている。

• まず最初に、合計 $0$ のときしかないことを意味する $1$ を用意する
• そこに $1$ を好きな回数足していいとして、$(1+x+x^2+x^3+\dots)$ を掛ける
• さらに $2$ も好きな回数足していいとして、$(1+x^2+x^4+x^6+\dots)$ を掛ける

ということは、$m=1$ のナップサック問題を解いた後、残りは以下のようにsliding window法で解ける。

• $(1+x+x^2+x^3+\dots)$ で割り、$(1+x^{L+1}+x^{2(L+1)}+x^{3(L+1)}+\dots)$ を掛けると $m=2$ の答え
• $(1+x^2+x^4+x^6+\dots)$ で割り、$(1+x^{L+2}+x^{2(L+2)}+x^{3(L+2)}+\dots)$ を掛けると $m=3$ の答え
• $(1+x^3+x^6+x^9+\dots)$ で割り、$(1+x^{L+3}+x^{2(L+3)}+x^{3(L+3)}+\dots)$ を掛けると $m=4$ の答え
• 以下略

ただし、計算量に問題がある。
毎回の計算をNTTで畳み込むと、$1$ 回あたり $O(N\log N)$ かかる。
$m=1$ のときの解を求めるのも含めて、$O(MN\log N)$ になる。
$M=5000,N=5000$ だと、計算時間がかなり厳しい。
そこでもう少し高速化して $\log N$ を消す。

$(1+x^{L+k}+x^{2(L+k)}+\dots)$ を掛けるのは、元々のナップサック問題で品物を $1$ つ追加するの処理と同等。
つまり、NTTではなく普通にナップサック問題の更新のやり方で畳み込めば、$1$ 回あたり $O(N)$ で終わる。
一方、$(1+x^k+x^{2k}+x^{3k}+\dots)$ で割る方も、 $\dfrac{1}{1-x^k}$ で割るということは、$1-x^k$ を掛ければよい。
これも、$2$ 項しかないので、愚直にやれば $O(N)$ である。
この両方をやり、$m=1$ も普通のナップサック問題の解き方に戻せば、計算量が全体で $O(MN)$ になる。

入力例1での動作

入力を受け取る。

n: 5
m: 3
l: 2

最初は、合計 $0$ の作り方だけが $1$ 通りなので、係数列を以下で初期化する。
$$
(1,0,0,0,0,0)
$$

$1$ 円硬貨を追加すると、係数列は以下になる。
$$
(1,1,1,1,1,1)
$$

さらに $2$ 円硬貨を追加すると、以下になる。
$$
(1,1,2,2,3,3)
$$

よって、$m=1$ の答えは合計 $5$ の係数である $3$。

次の窓へ移るため、$1$ 円硬貨に対応する因子を外す。
すると係数列は以下になる。
$$
(1,0,1,0,1,0)
$$

ここに $3$ 円硬貨を追加すると、以下になる。
$$
(1,0,1,1,1,1)
$$

よって、$m=2$ の答えは $1$。
したがって、順に $3,\ 1$ を出力する。

注意点

硬貨を追加する無制限ナップサックの更新は添字の小さい方から行う。
硬貨を外す更新は、更新前の係数を参照するため添字の大きい方から行う。

別解

特になし。