ABC422G - Balls and Boxes
ARCにも完全に同じタイトルの問題があるので紛らわしい。
問題概要
区別可能な $ 3 $ つの箱にボールを $ N $ 個入れるとき、ボールの個数がそれぞれ $ A $ の倍数、$ B $ の倍数、$ C $ の倍数になるような方法の個数を求めよ $ ( \operatorname{mod} 998244353 ) $ 。
ボール同士が $ ( 1 ) $ 区別できないとき、$ ( 2 ) $ 区別できるとき、それぞれ答えよ。
https://atcoder.jp/contests/abc422/tasks/abc422_g
考えたこと
$ N $ 以下の $ A $ の倍数を降順に見ていく。$ B $ の倍数と $ C $ の倍数に割り当てるべき残りのボールの個数 $ h $ は、非負整数 $ k $ を用いて、
$$ h = N - k A \notag $$
と表せる。また、これを非負整数 $ i , \, j $ を用いて、
$$ h = i B + j C \notag $$
と表したい。$ B , \, C $ が互いに素であるなら、
$$ i \equiv \frac { h } { B } \pmod { C } \notag $$
より、最小の $ i $ を求めることができる（互いに素でないなら、両辺を $ \gcd ( B , \, C ) $ で割ってから適用する）。$ B $ の倍数への割り当ては $ \operatorname{lcm} ( B , \, C ) $ 個ずつ増やすことができるから、単純な割り算で $ ( 1 ) $ は求められる。
$ ( 2 ) $ は、各 $ k $ に対して、
$$ \binom { N } { k A } \cdot \sum _ { t = 0 } \binom { N - k A } { i B + t \cdot \operatorname{lcm} ( B , \, C ) } \notag $$
を求めて、その総和が答えになる。
$ \operatorname{lcm} ( B , \, C ) \geq \sqrt { N } $ のときは $ t \leq \sqrt { N } $ であるから、愚直に計算すればよい。
$ \operatorname{lcm} ( B , \, C ) < \sqrt { N } $ のとき、愚直計算だと時間計算量が厳しいので少し工夫する。「 $ p $ 個のボールから $ q $ 個選ぶ方法のうち、$ q \equiv i B \pmod { \operatorname{lcm} ( B , \, C ) } $ であるようなものの総和を求める」と言い換えると、$ q $ の状態は $ \operatorname{lcm} ( B , \, C ) $ 個に限られるので DP に帰着できる。ボールを $ 1 $ 個追加するときに $ B $ の倍数に { 割り当てる、割り当てない } の $ 2 $ 通りしかないため、ボール $ 1 $ 個あたり $ O ( \sqrt { N } ) $ 回の計算で遷移できる。
提出コード
定数倍の軽い平方分割なので fastest が取れる。ほげ〜。
