ABC 401-500/ABC453E - Team Division - 競技プログラミング用 知識集積所

---

問題

ABC453E

必要知識

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

• 順列組み合わせ※
• 二項係数※
• 剰余類環
  • 繰り返し二乗法※
• 階差数列※

考え方

まずは愚直解を考えてみる。
チーム1にi人、チーム2にn-i人いるパターンは、以下で求められる。

• 各人について、チーム1にしか所属できない、チーム2にしか所属できない、どちらもいける、のいずれか判断する

 - どちらもダメという人が1人でもいたら、その時点で答えは0

• 片方にしか所属できない人は、全部そのチームに固定する
• どちらでもいい人が何人中何人チーム1に入ってほしいか考える
• 二項係数※でパターン数を求める

これをi=1からi=N-1まで全部やれば、（O(N^2)かかることを無視すれば）正解できる。

あとはこれの高速化をすればよい。
時間がかかっている原因は、「チーム1にしか所属できない、チーム2にしか所属できない、どちらもいける、のいずれか判断する」のを毎回やっている点。
似たような人数なら似たような結果になることを考えると、これを高速な区間加算でやればよいことがわかる。
よって、ここに階差数列※の知識を用いればよい。

LとRの値によって、区間加算する位置と順番が、つまり階差数列※のいじり方が4パターンある。
間違いがないように丁寧に実装すること。

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

解答例

解答例

注意点

別解