AT_k2pc001_h4 マシュマロ(Marshmallow)

[problemUrl]: https://atcoder.jp/contests/k2pc-hard/tasks/k2pc001_h4 kagamizは, ペットのミズゴロウと毎日家から $ K $ m 離れた公園まで散歩をしている. このとき, kagamizは往路と復路で, ミズゴロウと次のようなゲームをする: - $ 1 $ m 先か $ 2 $ m 先にマシュマロを投げ, ミズゴロウがそのマシュマロをキャッチする. - 投げた先にkagamizも移動し, 同じ操作を繰り返す. ただし, このときに, 公園より後の地点や, 家より前の地点にマシュマロを投げることは許されない. また, 往路でのスタート地点は 家から $ 0 $ mの地点, 復路でのスタート地点は 家から $ K $ mの地点であり, ここには必ず訪れることとなる. しかし, 往路のうち $ P $ 個の地点, 復路のうち $ Q $ 個の地点, 合計 $ R $ 個の地点には水たまりがあり, せっかくのマシュマロが濡れてしまい, ミズゴロウが水たまりで遊ぶためそこから動かなくなってしまう. したがって, 水たまりがある地点にマシュマロを投げることはしない. このとき, kagamizとミズゴロウが, 全ての地点にマシュマロを投げ散歩をする方法は何通りあるだろうか. あなたの仕事は, $ K $ , $ R $ , および水たまりができる地点の情報が与えられるとき, $ K $ m ある地点すべてにマシュマロを投げて, 散歩をする方法の数を $ 100000 $ で割ったあまりを kagamizに教えてあげることである. 与えられた条件のもと, 散歩をする方法の数を, $ 100000 $ で割った余りを出力せよ. - $ 1\ ≦\ K\ ≦\ 3000000 $ 家から公園までの距離 - $ 0\ ≦\ R\ ≦\ 100000 $ 往路または復路にある水たまりの個数の総数 - $ 1\ ≦\ a_i\ ≦\ K $ 家から水たまりがある地点までの距離 - 往路か復路を表す整数 $ t_i $ は, 必ず $ 1,2 $ のいずれかである. 配点の $ 30% $ 分については, $ R\ =\ 0 $ を満たす. 配点の $ 20% $ 分については, $ K\ ≦\ 15 $ を満たす. 配点の $ 10% $ 分については, これら $ 2 $ つの条件を両方満たす. 配点の $ 40% $ 分については, これら $ 2 $ つの条件の少なくとも一方を満たす. $ ※30%+20%+10%+40%=100% $という意味ではないことに注意せよ. ``` 3 0 ``` ``` 7 ``` ``` 14 2 1 9 2 3 ``` ``` 7105 ``` ``` 1 1 2 1 ``` ``` 0 ``` 復路の出発点は必ず $ K $ mの地点であることに注意せよ. ``` 3 2 1 1 2 1 ``` ``` 0 ``` この入出力例では, 家から $ 1 $ m 離れている地点に, 往路・復路ともに水たまりがある. したがって, すべての地点に訪れる事ができないので, $ 0 $ を出力する.

N/A

N/A