Project Euler

問題文は，リンクのProject EulerやProject Euler - PukiWikiを参照して下さい．

■101
(x_i, y_i)の対から，多項式の係数を求める公式があった気がするけど忘れてしまったので，
Ax=y
の形の方程式に変形して(掃き出し法で)解いた．
y_i=f(x_i)=Σ_0≦k≦na_kx_i^k
とした時，A_{j, i}は(j+1)ⁱ，x_j=a_j，y_j=f(x_j)となる(Aとyが既知)．

■102
外積で簡単に解ける．
原点をO，3頂点をA，B，Cとする．この時，
OA×OB，OB×OC，OC×OAの符号が全て一致⇔三角形ABCは原点Oを含む．
(適当な図について，A×B=|A||B|sinθを考えれば分かる)

■104
下9桁と上15桁程度を保存しておき，そこだけを更新し逐一判定．

■113
[桁数][一番左の数字]=増加数or減少数の個数でDP．
初期条件は，
増加数[0][9]=1，減少数[0][0]=1
上で求めた値の和から，増加数かつ減少数の個数を引けば良い．