Codeforces Beta Round #79 (Div. 1 Only)

Codeforces

珍しく（というか初めて？）深夜2時から2時間。
ABCでpretest通過したくせに、

で0完と結果は惨敗だったが、Cだけ解法を載せておく。そしてBの解法が知りたい。。
Bの解法は何人かの手助けのおかげで理解することが出来た。感謝。BITを使う。BITの葉をバスの始点と終点、さらに0とnでの組合せ数とする。終点でソートしてBITを使ってその地点で降りる組合せ数（始点から終点-1までの区間での組合せの総和）を計算する。葉の左から右へ値を更新していくイメージ。

C. Vectors

問題概要

ベクトルA,B,Cが与えられる。
ベクトルAを任意の回数だけ90度回転したりベクトルCを足したりして、ベクトルBが作れるか答えよ。

解法

ベクトルAの最初の向きを決めれば、4方向のベクトルCを何回かずつ足すことで、全てのベクトルの1/4?作ることが出来る。
さらにベクトルAの最初の向きを4方向全て試せば、全てのベクトルを作ることが出来る。
初期のベクトルAの向きを元のままとするときのみを考える。
ここで、A=(x_a,y_a), B=(x_b,y_b), C=(x_c,y_c)とする。
また、ベクトルCのそのままの向き、90度回転させた向き、180度回転させた向き、270度回転させた向きについて、足す回数をそれぞれp_0,p_1,p_2,p_3とする。
すると、
\left\{\begin{array}{l}x_a+p_0x_c-p_1y_c-p_2x_c+p_3y_c=x_b \\y_a+p_0y_c+p_1x_c-p_2y_c-p_3x_c=y_b\end{array}\right.
ここで、P=p_0-p_2, Q=p_3-p_1, X=x_b-x_a, Y=y_b-y_aとすれば、
\left\{\begin{array}{l}Px_c+Qy_c=X\\Py_c-Qx_c=Y\end{array}\right.
となる。
ここで、P,Qは任意の整数を取ることが出来るから、この連立方程式が整数解を持つかどうか調べればいいことになる。
P, Qについて解くと、
P=\frac{x_cX+y_cY}{x_c^2+y_c^2}
Q=\frac{y_cX-x_cY}{x_c^2+y_c^2}
これが整数になる、つまり分母で分子が割り切れれば、ベクトルAのその向きからベクトルBが作れることになる。
ベクトルAを4方向試せば終わり。