競技プログラミング用 知識集積所
ABC422G - Balls and Boxes
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
問題1
問題が、いかにも形式的べき級数※の出番。
Pa(x) = 1 + x^a + x^(2a) + x^(3a) + …… Pb(y) = 1 + y^b + y^(2b) + y^(3b) + …… Pc(z) = 1 + z^c + z^(2c) + z^(3c) + ……
として、これら3つの積を考える。
x^(ia)*y^(jb)*z^(kc)という項が、Aをia個、Bをjb個、Cをkc個という選択に対応すると考える。
すると、全部でn個入る入れ方は、yやzもxに変えたPa(x)*Pb(x)*Pc(x)の、x^nの係数を調べればよい。
これはn+1乗以上を適切に切り捨てながらの畳み込み※で実現できる。
x^(ia)*y^(jb)*z^(kc)という項が、Aをia個、Bをjb個、Cをkc個という選択に対応すると考える。
すると、全部でn個入る入れ方は、yやzもxに変えたPa(x)*Pb(x)*Pc(x)の、x^nの係数を調べればよい。
これはn+1乗以上を適切に切り捨てながらの畳み込み※で実現できる。
問題2
問題1と比べて、x^(ia)*y^(jb)*z^(kc)に(ia+jb+kc)!/{(ia)!*(jb)!*(zc)!}をかける必要がある。
よって、
よって、
Pa(x) = 1 + x^a/a! + x^(2a)/(2a)! + x^(3a)/(3a)! + …… Pb(y) = 1 + y^b/b! + y^(2b)/(2b)! + y^(3b)/(3b)! + …… Pc(z) = 1 + z^c/c! + z^(2c)/(2c)! + z^(3c)/(3c)! + ……
で同じように畳み込み※をして、x^nの係数にn!をかければよい。
答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。
また、階乗が何度も登場するので、事前に必要なだけ求めてメモ化しておくとよい。
