ABC 401-500/ABC405E - Fruit Lineup - 競技プログラミング用 知識集積所【5/17更新】

問題

ABC405E

必要知識

B以下レベルの内容は省略

• 二項係数（未作成）
• 順列組み合わせ（未作成）
• 剰余類環

考え方

力ずくでやるのは無謀なので、まずは少ない個数で手計算。

リンゴ1、オレンジ2、バナナ1、ブドウ1の場合、以下のように9個になる。

番号	並び順
1	リンゴ	バナナ	オレンジ	オレンジ	ブドウ
2	リンゴ	オレンジ	バナナ	オレンジ	ブドウ
3	リンゴ	オレンジ	オレンジ	バナナ	ブドウ
4	リンゴ	オレンジ	オレンジ	ブドウ	バナナ
5	オレンジ	リンゴ	バナナ	オレンジ	ブドウ
6	オレンジ	リンゴ	オレンジ	バナナ	ブドウ
7	オレンジ	リンゴ	オレンジ	ブドウ	バナナ
8	オレンジ	オレンジ	リンゴ	バナナ	ブドウ
9	オレンジ	オレンジ	リンゴ	ブドウ	バナナ

リンゴとバナナを両方赤に、オレンジとブドウを両方橙に塗ると、こうなる。

番号	並び順
1	リンゴ	バナナ	オレンジ	オレンジ	ブドウ
2	リンゴ	オレンジ	バナナ	オレンジ	ブドウ
3	リンゴ	オレンジ	オレンジ	バナナ	ブドウ
4	リンゴ	オレンジ	オレンジ	ブドウ	バナナ
5	オレンジ	リンゴ	バナナ	オレンジ	ブドウ
6	オレンジ	リンゴ	オレンジ	バナナ	ブドウ
7	オレンジ	リンゴ	オレンジ	ブドウ	バナナ
8	オレンジ	オレンジ	リンゴ	バナナ	ブドウ
9	オレンジ	オレンジ	リンゴ	ブドウ	バナナ

つまり、

• A+C個の赤マスと、B+D個のオレンジマスを用意する
• 赤マスの左からA個にリンゴを置き、残りにバナナを置く
• 橙マスの左からC個にオレンジを置き、残りにブドウを置く

とすることで、「リンゴはすべて、ブドウよりも左側に並べる。」以外を満たすパターンを過不足なく並べることができる。
その中で、リンゴが全てブドウより左にある、つまり左からA番目の赤マスが左からB+1番目の橙マスより左にある個数を数えればよい。
それらを左からA番目の赤マスの左に橙マスが何個あるかで分類して合計する。

橙マスの個数	左側の並べ方の数	右側の並べ方の数
0個	Comb(A-1,A-1)	Comb(B+C+D,C)
1個	Comb(A,A-1)	Comb(B+C+D-1,C)
2個	Comb(A+1,A-1)	Comb(B+C+D-2,C)
…	…	…
B-1個	Comb(A+B-2,A-1)	Comb(C+D+1,C)
B個	Comb(A+B-1,A-1)	Comb(C+D,C)

左と右を掛けたものの総和を取ればいい。

あとは、2*(B+1)個の二項係数（未作成）を高速で計算する方法だが、

• 階乗を(B+C+D)!まで先に全部計算して、Comb(x,y)=x!/(y!*(x-y)!) で計算する
• Comb(x,y)*(x-y)=Comb(x-1,y)*x を用いて順次計算する

などが使える。

答えは998244353で割ったものを要求されているので、剰余類環も参照。

注意点

別解