A2. Burenka and Traditions (hard version)
操作は長さ 1 または 2 としてよいです（$3$ 以上の操作は $n-2$ と $2$ に分割してよいという要領）．
長さ 2 で操作するものを辺で結ぶとパスに分解できます．$n$ 頂点のパスは総和が $0$ であるようなパスだけ $n-1$ 回，そうでなければ $n$ 回でできます．後者のパターンは長さ $1$ のパスに分解できるので，長さ $1$ のパスと，総和が $0$ であるようなパスでの遷移をすればよいです．
B. Fibonacci Strings
たいていの場合，最後の $f_k$ の個数以上を持つ文字は唯一に決まってそれを当てはめるしかないです．例外として，
- 21個：[1], 1, [2], 3, [5], 8, [13], 21
- 21個：1, 1, 2, 3, 5, 8, 13, [21]
のように末尾をとらなくても $f_k$ 以上の個数が実現できる場合があります．そのようなパターンでも $f_k$ 以上であるもの $2$ 種の個数が等しいので，置ける種類のうち最大の個数を末尾に割り当てることにしまってよいです．
C. Tonya and Burenka-179
$d<n$ かつ $d\mid n$ を満たす $d$ と $0\leq i<d$ をとって，mod d で $i$ のところを $n/d$ 個ずつ足すというのが動作です．
最大化を考えるにあたり，$d$ は可能ならば倍数に取り換えた方が得です（最大値は平均値以上であるという理屈）．よって，$p$ を素数として $d=n/p$ のパターンだけ考慮すればよいです．
D. Permutation for Burenka
$p$ について cartesian 木をとります．木が与えられて，いくつかの頂点の値が定まっていて，親子の大小関係が適切になる（親が subtree max になる）ように残りを補完するという問題になります．
値が未定の各頂点 $v$ について，既存の値との比較によって $L[v]$ 以上 $R[v]$ 以下になっていて欲しいという $L, R$ が定まります．$L$ は subtree max で，$R$ は root からの path min です．
これらはそのままでは十分条件ではないですが，各 $v$ で $L[v]$ 以上 $R[v]$ 以下になるように値を割り当てることに成功した場合，値を並べ替えて条件を満たすようにできます．親子関係のある区間同士には単調性があり，成功する場合には適当な貪欲法で割り当てなおせば子に小さい値が割り当てられるからです．
よって木の問題を忘れて，区間群と点群のマッチングという問題になります．あとはマッチングが成立する追加要素の最小値と最大値を求めればよいです．
E. Impressionism
次のようなグラフの問題になります．
$H+W$ 頂点の二部グラフが $2$ つある．辺には色がついている．同じ頂点に対して同じ色の辺はひとつ以下であることが保証される．
これらが（部集合を保つ）同型であるとして，左側集合同士・右側集合同士の同型対応を求めよ（または同型でないことを確かめよ）．
頂点の対応が一組決まると，その連結成分が決まったり矛盾したりします．
矛盾なく決まった場合には，同型な連結成分が見つかったことになり，（他の対応が条件を満たすかもしれないですが）決まった部分は確定してしまって大丈夫です．
以下 $H\leq W$ として説明します．最初に孤立点を前処理しておきます．すると，残った連結成分には必ず左側の点が存在します．未確定の点 $v$ をひとつとり，対応先 $H$ 通りをすべて試します．
$1$ 回あたりの「試す」計算量は適切に実装すれば，$v$ を含む連結成分の頂点数と辺数の和でおさえられます．対応先 $H$ 通りをすべて試行すれば，全体で計算量 $O(H^2W)$ で抑えられて成功ということになります．
各頂点の近傍の情報を，(色, 頂点) の組のソート列で持っておけば，同型で対応する頂点の近傍情報は同じ色順で並ぶはずなので，対応の確認が簡単になります（特に余計な log や hashmap は登場しません）．
F. Burenka, an Array and Queries
$2$ 乗解法の高速化で通したし，そういう雰囲気の解法が書いてあるように見える．
列 $a$ の要素はすべて素数としてよいです．mo を使うことにして，単に素数ごとの出現頻度を持っておきます．あとは求値クエリひとつひとつが十分高速なら大丈夫です．
$P$ を総積として，$\sum_{b\mid P}\mu(b)\cdot \lfloor C/b\rfloor$ です．
$b$ は当然 square-free なものだけ計算すればよいです．$b=p_1\cdots p_k$ と書けますが，これを $b=ap$ と表します（$p=p_k$ は最大素因数）．
このとき $a$ の種類数は少ない（multiplicative function の sum を求める black’s algorithm と同様）ことから計算します．
本問の $C$ の制約で $a$ は $600$ 種ほどしか存在せず，それらが総積 $P$ の約数であるか否かを判定することは十分高速に行えます．
あとは $\sum_j [cnt[j]>0] \lfloor C/p_j\rfloor$ のような区間和を計算すればよくて，ここは ループ範囲と $C/p_j$ を前計算しておけば十分高速でした．
基本的には 「$C$ 以下かつすべての素因数が $m$ 以下」というすべての $b$ に対する sum を（判定以外は）まとめずに足しているという解法なので，求値ごとに $49000$ ループくらいまわっているはずです．これは FOR(j, S[i], T[i]) x += vals[i][j] * exist[j]; というかなり軽い処理なので大丈夫という仕組み．
