atcoder#ABC280G. [ABC280G] Do Use Hexagon Grid 2
[ABC280G] Do Use Hexagon Grid 2
配点 : 点
問題文
以下のような、無限に広い六角形のグリッドがあります。
六角形のマスは つの整数 を用いて と表されます。 マス は以下の つのマスと辺で隣接しています。
つのマス の距離を、辺で隣接しているマスをたどってマス からマス まで移動するときの、移動回数の最小値と定めます。 例えばマス とマス の距離は 、マス とマス の距離は です。
個のマス が与えられます。 この マスの中から つ以上のマスを選ぶ方法のうち、選んだマスのうちどの マスの距離も 以下になるようなものは何通りありますか? で割ったあまりを求めてください。
制約
- は相異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
3 1
0 0
0 1
1 0
5
選ぶマスの集合として考えられるのは $\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\}$ の 通りです。
9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
33
5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482
31