yukicoder No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
お題箱より。
No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder
解法
箱を並び替えても答えが変わることはないので、 の昇順に並べておきます。
各箱から玉を1個ずつ取り出し、ある1つの色 の玉がちょうど 個選ばれる場合の数が、どのように計算できるか図示してみましょう。
の昇順に並べたことによって、箱は色 の玉を含まないゾーンと含むゾーンに分かれます。含まないゾーンの取り出し方は の積であり、色 の玉はもちろん 個です。
色 の玉を含むゾーンの取り出し方は以下のDPによって求めることができます。
- 箱 全てに色 の玉が1個ずつ含まれているとき、これらの箱から玉を1個ずつ取り出し、色 の玉がちょうど 個選ばれる場合の数。
この値は、箱 の全てに含まれている色であればどの色でも同じ値になります。つまりクエリで必要な色 全てについて別々に計算する必要がありません。
初期条件は で、後ろから求めていきます。遷移は
- を遷移元とし、箱 から色 の玉を選ぶ。係数 で に遷移。
- を遷移元とし、箱 から色 でない玉を選ぶ。係数 で に遷移。
となります。DPパートの計算量は です。
クエリに答えるには「ある1つの色 の玉がちょうど 個選ばれる場合の数」をたくさんの について求める必要があります。これは以下のように計算することができます。
- まず、箱が色 を含まないゾーンと含むゾーンの境界を二分探索で探す。色 を含む箱の最小のインデックスを とする(存在しない場合は )。
- 色 を含まないゾーンの選び方は なので、事前に累積「積」を計算しておいてそれを参照する。
- 色 を含むゾーンの選び方はDPテーブルを参照する。具体的には である。
これは1つの あたり で計算できます。必要な の個数は なので、ちょっと厳しいですが間に合います。
ACコード
No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder
公式解説では多項式の係数として解説していますが、1次式を掛けた時の係数の計算と今回のDPは全く同じものなので、解法としては同じです。