競技プログラミング用 知識集積所
ABC458E - Count 123
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず、1と2と3を条件のように並べるというのは、
- 2をとりあえず全部並べる
- 2と2の間（両端含む）のうち、i箇所を選ぶ
- 選んだi箇所に、1をわけて詰め込む（選んだところ全てに1を最低1個は入れる）
- 残りのX2+1-i箇所に、3をわけて詰め込む（空になるところがあってもよい）
を1以上X2以下の全てのiについて考えて合計すればよい。
それぞれは順列組み合わせ※の基本的問題であり、
Σ[i=1..X2] comb(X2+1,i)*comb(X1-1,i-1)*comb(X3+X2-i,X2-i)
をやればよい。
ただし、comb(n,r)が、n<rのときに0を返すようにしておくこと。
ただし、comb(n,r)が、n<rのときに0を返すようにしておくこと。
答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
特に、3つ掛け算するのはlong long型からすらはみ出るので、必ず2個かけた段階で一旦%998244353することを忘れずに。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
特に、3つ掛け算するのはlong long型からすらはみ出るので、必ず2個かけた段階で一旦%998244353することを忘れずに。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。
