FPS24 A - お菓子
考え方
コンテストトップページに $H$ 問題までは知識を必要としないと書かれている。
しかしこれは大嘘で、序盤からいろいろな知識やテクニックを要求してくる。
序盤で使うあたりのことは別記事にまとめたので、「形式的冪級数」の記事参照。
$A$ 問題では、上のリンク先の記事で、少なくとも以下の $4$ 項目を理解する必要がある。
- 形式的冪級数
- 通常型母関数
- 畳み込み
- 組み合わせ問題への適用
上記をすべて理解している前提で解説を行う。
$1$ 日のお金の使い方は、$1$ 円、$3$ 円、$4$ 円、$6$ 円 が $1$ 通りずつで、残りは $0$ 通り。
よって、その母関数は $x+x^3+x^4+x^6$ と表せる。
すると、$D$ 日間でのお金の使い方は、$(x+x^3+x^4+x^6)^D$ で表せる。
このうち、$x^N$ の係数を答えればよいことになる。
問題はその係数をどのように求めるか。
わかりやすい方針は $2$ つある。
わかりにくい高度な方針なら他にもあるが、ここではそれは見なかったことにする。
方針 $1$
冒頭の $4$ 項目の知識だけで求める。
つまり、人力で畳み込みをしやすくするための式変形を頑張る。
$x+x^3+x^4+x^6 = x(1+x^2)(1+x^3)$ と変形できるので、$(x+x^3+x^4+x^6)^D=x^D(1+x^2)^D(1+x^3)^D$ となる。
これの $x^N$ の係数というのは、つまり、$(1+x^2)^D(1+x^3)^D$ における $x^{N-D}$ の係数である。
それぞれの $D$ 乗を二項展開すると、以下のような式になる。
$$
({}_D\mathrm{C}_0+{}_D\mathrm{C}_1x^2+{}_D\mathrm{C}_2x^4+\dots+{}_D\mathrm{C}_Dx^{2D}) \times
({}_D\mathrm{C}_0+{}_D\mathrm{C}_1x^3+{}_D\mathrm{C}_2x^6+\dots+{}_D\mathrm{C}_Dx^{3D})
$$
この式の畳み込みは、素直に指数の和が $N-D$ になる組を拾って、係数の積の総和を求めればよい。
コード部分は二項係数ライブラリさえあればシンプルで、階乗の事前計算分に加えて $O(D)$ である。
「解答例」参照。
方針 $2$
冒頭の $4$ 項目よりは少し発展的な知識を使って力技で求める。
つまり、NTTによる畳み込みを用いて、繰り返し二乗法で $D$ 乗を計算する。
$x^{N+1}$ 以上は意味がないのでそこから先は途中で切り捨てながら求める。
計算量は $O(N\log N\log D)$ となる。
「解答例2」参照。
入力例1での動作
入力を受け取る。
d: 2
n: 7方針 $1$ では、$(1+x^2)^2(1+x^3)^2$ の $x^{N-D}=x^5$ の係数を求める。
$x^3$ を $i$ 回取るとする。
$i=0$ では、残りの次数は $5$ であり、$x^2$ だけでは作れないのでスキップする。
$i=1$ では、残りの次数は $5-3=2$ なので、$x^2$ を $1$ 回取ればよい。
この選び方は、${}_2\mathrm{C}_1\times{}_2\mathrm{C}_1=2\times 2=4$ 通りである。
$i=2$ では $3i=6>N-D=5$ となるので、これ以上調べる必要はない。
以上より、答えは $4$ となる。
注意点
二項係数は $998244353$ で割った余りを求めながら計算する。
階乗を用いて二項係数を求める際の除算には逆元を用い、逆元は繰り返し二乗法で求める。
別解
特になし。