A. Simons and Making It Beautiful
先頭が $N$ になるようにスワップするとスコアを最小化できます．
B. Simons and Cakes for Success
素因数分解して素数ごとに考えると，$k$ は $p$ をいくつ以上含むという条件がでてきます．
（結局「いくつ以上」は単に $1$ 以上なはず）
C. Simons and Posting Blogs
逆順に見た上でそれぞれ reverse などすると言い換え問題文は，「結合して，同じ値の $2$ 回目以降を捨てる．結果を辞書順最小化」というものです．
結合して辞書順最小化，と思うと文字列の $X+Y<Y+X$ のソートのような何かが登場しそうな気もしましたが，あまり関係ありません．
とりあえず単に辞書順最小のもの $X$ を採用しようとします．これが最適でなくなるとすると，結合の場合には $X$ を prefix にもつ $Y$ が別の候補ということになります．しかしこの出現を unique する設定では，$Y$ を使うパターンは $X\to Y\to \cdots$ に置き換えられるので，考えなくてよいです．
結局辞書順 min を使うことを確定させてよいです．あとは既出の要素を削除して解きます．
$x=\sum l_i$ とすれば，「既出要素削除」は $O(x^2)$ です．ある文字を削除するときに残り文字を一回ずつ見るので．
辞書順 min ですが，これも一回あたり $O(x)$ で全部で $O(nx)$ です．「$2$ 個を比較して大きい方を捨てる」ことを繰り返しますが，比較には短い方の長さの計算量しかかかりません．「$2$ 個を比較して，大きい方を捨てる．捨てた方の長さをコストと見なす．」とすればよいです．
D. Simons and Beating Peaks
max について，「左側全削除」または「右側全削除」をするしかありません．これで再帰的に解きます．
結局 Cartesian Tree の高さになると思いますがあまり気にせず解きました．
E. Simons and Dividing the Rhythm
$rev(S)$ を reverse とします．
文字列の border とは，prefix でも suffix でもあるような部分文字列のことでした（空でないことと全体と一致しないことも要求します）．結論として，borderless substring への分割を数えればよいです．
まず，borderless substring への異なる分割からは異なる文字列が得られることを示します．
$T=X+A+B+\cdots=Y+C+D+\cdots$ を $2$ つのそのような分割とし，$|X| < |Y|$ とすれば
- $X$ は $Y$ の prefix
- $rev(X)$ が $rev(Y)$ の prefix つまり $X$ が $Y$ の suffix
より $X$ は $Y$ の border となって，borderless への分解であることに矛盾します．よって $X=Y$ で，これを繰り返すと示せます．
次に，任意の操作結果について，同じ操作結果を得るような borderless substring への分割がとれることを示します．
これは border を持つ文字列を操作結果を保つように分割していくという方針で示せます．（例えば $abcab \to bacba$ という操作は $ab,c,ab$ に分割して操作するというものに置き換えられます．）
$T$ が $S$ の border で，$|S|=n,|T|=m$ であるとします．このとき $S$ は周期 $p=n-m$ を持ちます．
$m\leq n/2$ なら $S=TUT$ と書けるので，$rev(S)=rev(T)rev(U)rev(T)$ と操作を分割できます．
$n/2 < m$ のときは，周期 $p=n-m$ の何倍かを引いた $m-kp$ も border となります．このことから，border として常に長さ半分以下のものがとれるので，上の議論が使えます．
F. Simons and Dividing the Rhythm
感覚的には，各頂点の次数が偶数であるような境界線によって，図形全体が内外の $2$ 種に分かれます．
グラフ理論と幾何学的に示します．境界線はすべての頂点の次数が偶数なので，サイクルの和として書けます．サイクルは平面上の単純多角形で，ある点から半直線方向に進んで交わる回数の偶奇は一定です（進む方向を微小に変化させるタイプの議論で正当化可能）．この偶奇で内外を定義すればよいです．
あるいは問題文の定義を利用できて，そちらの方が初等的でいいかも．ちょうど「上方向，左方向の境界線の個数の偶奇」の概念が定義されています．
この偶奇が全マスで一致することを示したいのですが，不一致なマスが存在したとしてその辞書順最小のところに注目すると，矛盾します（左のマス，左上のマス，上のマスでは一致していたことから次数奇数の点が発生）．
言い換え問題文．
- 各マスを $0$ または $1$ とする．
- $0,1$ の境界となる辺を境界線として採用．
さらに言い換えると，
- 各マスを $0$ または $1$ とする．
- 各マスについて「上，左の辺の値をプラス，右，下の辺の値をマイナス」とした辺の値の総和を各マスの重みとする．
- $1$ とした全マスの重み和がスコアとなる．
という形になります．まずここは境界線にできない，という制約を無視すれば，重みと $0$ の $\max$ を足していくと答になります．境界線に関する制約は，「あるマスは $0$ としてください」「こことここは同じ $0,1$ にしてください」というタイプの制約です．連結成分ごとの重み和などを求めればよいです．
G. Simons and Diophantus Equation
まず，GCD に関することなので，包除原理を行うための $2$ つの定義をします．$d>0$ に対して
- $f(d)$：$\gcd(i\oplus j,j\oplus k)=d$ となる $(i,j,k)$ の数え上げ．
- $g(d)$：$d\mid \gcd(i\oplus j,j\oplus k)=d$ かつ $d\mid \gcd(i\oplus j,j\oplus k)$ となる $(i,j,k)$ の数え上げ．
通常は $f$ が欲しいもの，$g$ が計算しやすいものです．これらの関係は $g(d)=\sum_{d\mid x} f(x)$ です．
$g$ は $f$ を倍数関係についてゼータ変換したものです．逆に言えば $f$ は $g$ の倍数関係に関するメビウス変換です．
答は $g(d)$ の線形結合なので，$f(d)$ の線形結合でもあります．まず，$ANS=\sum_d c_df(d)$ となる係数 $c_d$ が求まります．
（すべての $f(d)$ を求めたあとメビウス変換をして $g(d)$ を求めるという手順も考えられます．$c_d=0$ となる $d$ がたくさん出てくる場合には定数倍の差が出るかもしれません．この問題では最悪ケースについてはほとんど差が出ないと思います．）
結局，すべての $d$ に対する $f(d)$ を十分高速に求められれば良いです．$j＄ ごとにこれを計算しようとすると，$f(d) = \sum _ j n _ {d, j} ^ 2$ の形です．
$d$ の倍数 $x$ を固定するごとに，$n_{d,j}$ への加算を行うとします．これは添字集合 $\lbrace j\mid j, j\oplus x \leq M\rbrace$ に対する $1$ の加算です．
このような区間は $O(\log M)$ 個の区間に分割できるため，次のような形になります．
- 配列 $(n_0,n_1,\ldots,)$ が $0$ で初期化されている．
- $d$ の倍数 $x$ について反復．それぞれの $x$ について $O(\log M)$ 個の区間が登場．区間に対して $+1$ 加算をする．
- $\sum n_j^2$ を求めよ．
これでぱっと見では $O(M\log^3M)$ 時間達成です．全部で $O(M\log^2 M)$ 個の区間への加算を行うことと $2$ 乗和の計算で，これは遅延セグメント木で扱えます．
ところで，全体の計算量を $O(M\log^2M)$ にすることもできるはずで，これは「$O(\log M)$ 個の区間への分割」を経由せずに直接「$j\mid j\oplus x\leq M$ を満たす $j$ に作用させる」ことができるからです．（よくあるインターフェースの遅延セグ木で同じ $x$ に対して $O(\log M)$ 個の区間に分割してから遅延セグ木を呼ぶと，同じ区間の遅延作用を何度もクリアしてしまっているはず．根から再帰的にもぐりながら区間を分割していけばこういうことは起きない．）
これはさぼって AC でした．ただし，$d$ が小さいときには大量の区間加算と $1$ 回の $2$ 乗和計算が行われるため遅延セグメント木を累積和に置き換えるなど，高速化の工夫は必要でした．
$O(M\log^2M)$ にしたら，$d$ の大小によって処理を分けなくても AC になりました．
