「FPS 24 題」全部解く: G「硬貨」

解きます

解く

一旦$m$を固定した状態で解きます. 求めるべきものは
$$f_m := \prod_{k=m}^{m+L-1}\frac 1{1-x^k}$$
としたとき$\left[x^N\right]f_m$ですね. 愚直にやれば$O(NL)$で求められます.
ただ, これを$M-L+1$回求める必要があり, これを毎回行っていては時間がかかりすぎます.

どうするかというと, 一旦$f_{m+1}/f_m$を計算してみます.
$$\begin{align}
\frac{f_{m+1}}{f_m}
&= \frac{\prod_{k=m+1}^{m+L}\frac 1{1-x^k}}{\prod_{k=m}^{m+L-1}\frac 1{1-x^k}} \\
&= \frac{\prod_{k=m}^{m+L-1}1-x^k}{\prod_{k=m+1}^{m+L}1-x^k} \\
&= \frac{\left(1-x^m\right)\left(1-x^{m+1}\right)\cdots\left(1-x^{m+L-2}\right)\left(1-x^{m+L-1}\right)}{\left(1-x^{m+1}\right)\left(1-x^{m+2}\right)\cdots\left(1-x^{m+L-1}\right)\left(1-x^{m+L}\right)} \\
&= \frac{\left(1-x^m\right)\cancel{\left(1-x^{m+1}\right)}\cdots\cancel{\left(1-x^{m+L-2}\right)}\cancel{\left(1-x^{m+L-1}\right)}}{\cancel{\left(1-x^{m+1}\right)}\cancel{\left(1-x^{m+2}\right)}\cdots\cancel{\left(1-x^{m+L-1}\right)}\left(1-x^{m+L}\right)} \\
&= \frac{1-x^m}{1-x^{m+L}}
\end{align}$$
大部分が共通してるので打ち消してこうなりました. つまり
$$f_{m+1}=\frac{1-x^m}{1-x^{m+L}} f_m$$
なので, 計算結果を$1-x^{m+L}$で割って$1-x^m$を掛けたら$m$が1だけ大きい結果が得られる, ということです. これにかかるコストは$O\left(N\right)$なので, $f_1$を愚直に求めたあとこれを繰り返して他の結果を得るようにすれば全体の計算量が$O\left(N M\right)$になります.

FPSという視点から離れて操作を見ると「$1-x^{m+L}$で割る」は「$m+L$円硬貨を使えるようにする」に, 「$1-x^m$を掛ける」は「$m$円硬貨を使えなくする」にそれぞれ対応します.

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
        m: usize,
        l: usize,
    }
    // fpsを定数関数1で初期化
    let mut fps = vec![Mint::raw(0); n + 1];
    fps[0] = Mint::raw(1);
    // f_1を求める
    for k in 1..=l {
        // 1-x^k で割る
        for i in k..=n {
            let temp = fps[i - k];
            fps[i] += temp;
        }
    }
    // f_1が求まったので, n次の係数を出力
    println!("{}", fps[n]);
    for m in 1..m - l + 1 {
        // 1-x^(m+l) で割る
        for i in m + l..=n {
            let temp = fps[i - m - l];
            fps[i] += temp;
        }
        // 1-x^m を掛ける
        for i in (m..=n).rev() {
            let temp = fps[i - m];
            fps[i] -= temp;
        }
        // f_(m+1)が求まったので, n次の係数を出力
        println!("{}", fps[n]);
    }
}

提出(34 ms):

終わり

数式弄りも頭の片隅で計算量を意識してやりましょうね
以上です