![? クエリで与えられる(?, ?)に対して、?? ? を
?? + ?? = ? となる格子点に書かれてる数の
和とすると、以下の漸化式が成立する
?? 0 = 1
??[?] = ??[? ? ?] + ??[? ? ?]](https://image.slidesharecdn.com/random-151117151944-lva1-app6891/85/IJPC-C-8-320.jpg)
![? この漸化式を用いることで、クエリ(?, ?, ?)に
対して、得られた??[0]～??[?]の値の合計が
求めるクエリの答えとなる](https://image.slidesharecdn.com/random-151117151944-lva1-app6891/85/IJPC-C-11-320.jpg)
IJPC C解説
- 2. ? 直線?? + ?? = ?と? = 0, ? = 0で囲まれた 領域に含まれる格子点に含まれる格子点 (?, ?)すべてに対する ?+? ? の和を求める
- 3. ? 直線?? + ?? = ?と? = 0, ? = 0で囲まれた 領域に含まれる格子点に含まれる格子点 (?, ?)すべてに対する ?+? ? の和を求める ? このようなクエリに?個答える
- 4. ? 直線?? + ?? = ?と? = 0, ? = 0で囲まれた 領域に含まれる格子点に含まれる格子点 (?, ?)すべてに対する ?+? ? の和を求める ? このようなクエリに?個答える ? 1 ≦ ?, ?, ? ≦ 10000 , 1 ≦ ? ≦ 1000000
- 5. ? とりあえずクエリに答えることを考える ? 座標の最大値を?とすると、毎回すべての座 標を見ると? ?2 個の座標を見ることになり 間に合わない ? ?座標ごとにまとめてCombinationの合計を求 められればよさそう
- 6. ? Combination の値は漸化式などを用いて ? ?2 ですべて計算できるので、?座標ごとに 累積和を計算しておく ? そうすることで、 クエリ毎? ? 前計算? ?2 で可能となる
- 7. ? 今度は別の方法でクエリ毎? ? に答えること を考える ? Combination の漸化式の性質を利用しよう
- 8. ? クエリで与えられる(?, ?)に対して、?? ? を ?? + ?? = ? となる格子点に書かれてる数の 和とすると、以下の漸化式が成立する ?? 0 = 1 ??[?] = ??[? ? ?] + ??[? ? ?]
- 9. ? 各座標(?, ?)に対して、そのマスには? + ?個 のものから?個選ぶ方法が何通りあるか書か れている ? つまり、これは?個の?と?個の?を並べ替える 方法と一致する
- 10. ? よって、?? + ?? = ? となる格子点に書かれて る数の和とは、すなわち、?と?を並べて合計 が?になる方法が何通りあるかと一致する ? これは簡単に動的計画法を行え、最後に並べ るのが?か?かの二通りの場合分けで所望の漸 化式が得られる
- 11. ? この漸化式を用いることで、クエリ(?, ?, ?)に 対して、得られた??[0]～??[?]の値の合計が 求めるクエリの答えとなる
- 12. ? 以上の二つの解法をまとめて使うことを考える ? 以下、クエリにおいて、?, ?の対称性から? ≧ ?であるとして考える ? このとき、? ≧ ?となるクエリに対しては、解 法(1)を用いて、 ? < ? なる (?, ?) に対しては、 すべてのクエリをまとめて解法(2)を用いる、 とする
- 13. ? このとき、解法(1) では、 前計算 ?(?2 /?) 毎クエリ ?(?/?) ? 解法(2) では、 クエリの後処理 ?(??2 )
- 14. ? よって、計算量 ? ? ?2 + ?+? ? ? これで、? = 3 ? + ? とおくことで、十分間 に合う計算量となる