ABC 401-500/ABC459E - Select from Subtrees - 競技プログラミング用 知識集積所

---

問題

ABC459E

必要知識

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

• 順列組み合わせ※
• 二項係数※
• 動的計画法
• 深さ優先探索※
• 剰余類環
  • 繰り返し二乗法※

考え方

木の先端から順に処理をしていく動的計画法、いわゆる木DP。
深さ優先探索※をしながら、先端側担当のリスから順に「自分は何個から選んでよいのか」を確定していく。
つまり、子の頂点に残っている飴を全て自分の頂点に移動させて、選択肢数を決めた後で、選んだ個数を引いてその頂点に残しておく。

各リスについて、n個からr個選ぶなら二項係数※nCrを求め、それらの総乗を取れば答え。
不可能な場合は0と答える点も、n<rならnCrが0になるようにコードを書けば自動的に解決する。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。

解答例

解答例

注意点

Cにlong long型を使用する。

飴を木の親側に送っていくと、多くの足し算の結果int型を超えることがある。

二項係数※の計算にオーバーフローケアが必要

二項係数※を求めるときに、nCrのnの方が10^14くらいある可能性がある。
掛け算の前に剰余を取らないと、long long型でさえオーバーフローする。

別解