- https://codeforces.com/contest/1225
- https://codeforces.com/contest/1246 (div1)
- https://codeforces.com/contest/1247 (div2)
書くのは div1 について．
A. p-binary
個数を決めた場合の判定は，$2^x$ の和を指定個数で目的の値にできるかというものです．これは目的の値の popcnt などから計算できます．可能な場合には $30$ 個以下程度でできることも分かります．
B. Power Products
素因数ごとの指数を mod k したもの標準形と呼ぶことにすると，まず標準形になおして，各値に対してどのような標準形が欲しいかもわかります．あとはハッシュを使って数えます．
C. Rock Is Push
同じ方向の移動はまとめて考えます．マス (x,y) に到達して，最後の移動が縦/横であるものを考える dp をします．それぞれの方向について区間和をとることで計算できます．そこで dp テーブルを計算しながら各行・列の累積和テーブルも同時に作っていきます．
D. Tree Factory
入力の木をパスにしていきます．葉をひとつとり，葉から根までのパスを見ます．次数 $3$ 以上の点のうち葉に一番近いところをいじってパスの長さを増やすことができます．
E. To Make 1
$\sum a_ik^{-b_i}=1$ となる列 $(b_i)$ の存在が必要です．これはなんと十分でもあります．$b_i$ の大きい方から有理数を足して分母を下げることを考えればよいです．
十分性の証明の構築から，構築手順は，何らかの順に一要素ずつ足していって好きなタイミングで $K$ を割ると思ってもよいです．これで順列に対する探索になるため，適当な bit dp で解けます（bitset 高速化も行う）．
F. Cursor Distance
すごい．
終点を固定します．操作を逆から見ます．戻り行き先は区間です．$n$ 回戻った先の区間を $[L_n, R_n]$ とするとき $\sum_n (R_n-L_n+1)$ を求めればよいです．
このシミュレーションは L, R について独立ではないので，共通の前計算で高速化するのは難しそうに思えます．しかし，次の $L$ や次の $R$ は，その区間内の文字種類数を決めると計算できてしまいます．なぜなら，文字種類数 $k$ を決めると $L$ に最も近い $k$ 種類の場所が決まり，そこから最適な左移動を選べばよいからです．
よって，文字種が一定である間の計算は $L$, $R$ それぞれについて独立に行えます．文字種が増えるかどうかも $L$, $R$ 独立に判定できます．
結局，functional graph （または有向木）を 2 つ作って，左右それぞれを文字種が増えるところまでのぼるという計算になります．
文字種が定数のときの計算をまとめて行えば，空間は $O(n)$ でできます．
