🔫

FPS24 G - 硬貨 勉強メモ

に公開
競技プログラミング
fps
tech

問題リンク

https://atcoder.jp/contests/fps-24/tasks/fps_24_g

問題概要

1 円硬貨、 2 円硬貨、 \cdots 、 M 円硬貨が無限にあります。同じ金額の硬貨同士は区別できません。

M - L + 1 個の問題についてそれぞれ解いてください。 m ~ (1 \leq m \leq M - L + 1) 番目の問題は以下の通りです。

m 円硬貨、 m + 1 円硬貨、 \cdots 、 m + L - 1 円硬貨を自由に使いちょうど N 円支払う方法の個数を 998244353 で割った余りを求めてください。
ただし、 2 つの支払い方は、払う枚数が 2 つの支払い方で異なる効果が存在するときに区別します。

制約

  • 入力される値はすべて整数
  • 1 \leq N, M, L \leq 5000

解説

[x^n]f_k を k 円硬貨のみを使って n 円支払う方法の個数としたとき、

f_1 = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}\\ f_2 = 1 + x^2 + x^4 + x^6 + \cdots = \frac{1}{1 - x^2}\\ f_3 = 1 + x^3 + x^6 + x^9 + \cdots = \frac{1}{1 - x^3}\\ \vdots\\ f_k = \frac{1}{1 - x^k}

となります。（等比級数の和の公式を思い出すと良いです。）

よって、 m 番目の問題の答えは、

F_m = f_m \times f_{m + 1} \times \cdots \times f_{m + L - 1}

なるべき級数 F_m に対する [x^N] F_m です。

この値は以下のように差分更新をすることで、 O(M + L) 回の計算で済みます。

F_{m + 1} = \frac{F_m \times f_{m + L}}{f_m}

また、これは掛け算・割り算の筆算の要領でやることで、各計算は O(N) 時間です。
（昇べきの順に係数を合わせるようなイメージで実装すると良いです。）

実装例(Python3)
Fps = list[int]
MOD = 998244353


def div(f: Fps, d: int) -> Fps:
    n = len(f)
    res = [0] * n
    for i in range(n):
        res[i] = f[i]
        if i + d < n:
            f[i + d] = (f[i + d] + res[i]) % MOD
    return res


def mul(f: Fps, d: int) -> Fps:
    n = len(f)
    res = [0] * n
    for i in range(n):
        res[i] = (res[i] + f[i]) % MOD
        if i + d < n:
            res[i + d] = (res[i + d] - f[i]) % MOD
    return res


N, M, L = [int(s) for s in input().split()]

f = [0] * (N + 1)
f[0] = 1

for i in range(1, L + 1):
    f = div(f, i)

for m in range(1, M - L + 2):
    print(f[N])
    f = mul(div(f, m + L), m)

https://atcoder.jp/contests/fps-24/submissions/75316585

所感

畳み込みと FPS inv を使うと TLE をして難しかった…。と思ったら N \leq 5000 としたときの O(N^2 \log N) はかなり無理そう。こういう筆算も実装できるようになるべき。

Discussion