- A. New World, New Me, New Array
- B. Having Been a Treasurer in the Past, I Help Goblins Deceive
- C. Creating Keys for StORages Has Become My Main Skill
- D. For Wizards, the Exam Is Easy, but I Couldn’t Handle It
- E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?
- F. Goodbye, Banker Life
- G. I’ve Been Flipping Numbers for 300 Years and Calculated the Sum
A. New World, New Me, New Array
ceil(K,p)
B. Having Been a Treasurer in the Past, I Help Goblins Deceive
ABA を最大化するとします．A を全部並べたところに B を好きに挿入すると考えます．挿入位置によってその文字を含む ABA の個数が決まるのでそれを最大化すればよいです．
C. Creating Keys for StORages Has Become My Main Skill
使えるのは $x$ の subset だけで，mex を大きくするためにそれを昇順に飛ばすことなく使っていきます．ただし全部の or が $x$ にならなかった場合には最後の項だけ妥協します．
D. For Wizards, the Exam Is Easy, but I Couldn’t Handle It
$n^2$ 通りすべての場合を計算します．$l$ を固定して $r$ をインクリメントしていきましょう．転倒数の変化は，$l,r$ の間にある $a_l$ より大きいもの・小さいものの個数の差から分かります．
E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?
$K = \sum \binom{n_i}{2}$ となる $n_1,n_2,\ldots$ をとり，各 $n_i$ 個内の全ペアが条件を満たすようにすればよいです．
F. Goodbye, Banker Life
$T$ には $k$, $0$ のどちらかしか現れず，$k=1$ の場合が本質です．
xor を加算に置き換えると $T$ は二項係数になるため，xor の場合には二項係数の偶奇です．よって $(1+x)^{n-1}$ の係数の偶奇を求めればよいです．$(1+x)^{2^k}=1+x^{2^k}\pmod{2}$ から高速に展開できます．（Lucas の定理という結果になる）
G. I’ve Been Flipping Numbers for 300 Years and Calculated the Sum
$n$ が $p$ 進法で $3$ 桁以上になる場合は個別処理しておきます（$O(\sqrt{n})$）．
残りの計算は $\lfloor n/p\rfloor$ が定数の部分をまとめて計算します．
