div2 only は省略
A. Cards
連長圧縮したときの o, x の個数を固定すると最適解が計算できます．
B. Painting The Wall
ある時点での状態は，少なくともひとつのマスが塗られた行の個数・列の個数によって表されます．すると $O(N^2)$ 頂点の DAG と遷移確率も簡単に分かっていて，ゴールするまでの回数期待値を求めるという問題になり，適当な DP で解けます．
C. Tree and Array
$2n$ 頂点増やすと good pair が $n$ 組増える．という構造があればよいです．$N$ 頂点の木で頂点 $N$ が good pair に使われていないときに，$N+2n$ 頂点の木で頂点 $N+2n$ が good pair に使われていないようなものを作ろうとします．これには適当な $2n$ 頂点のパーツがあればできます．
あとは探索です．$N$ が十分大きければ $8$ 頂点増やせることが分かり，小さいところも乱択で見つけて埋め込みました（$t$ の値がかなり小さい範囲で探索すると結構たくさん解があることが分かります）．
D. Instant Messanger
辺は頂点次数の小さい方から大きい方に向き付ければ，各頂点の出次数は小さいです．入ってくる辺による答は保持しておき，出ていく辺による答はクエリが来たときにとってくるようにします．
E. Sorting Permutations
問題文 2 文目で与えられる $k$ と，問題文後半および Input で与えられる $k$ は無関係！！！！
2 回で作れるパターンがどういうものかを考えます（結論すべての順列が作れることが分かります）．$1$ 回目でスワップさせる組に色 $1$ の辺，$2$ 回目でスワップさせる組に色 $2$ の辺を張ると，各連結成分は「交互パス」「交互サイクル」のどちらかになります．交互パスからはひとつのサイクルが作られ，交互サイクルからは長さが半分のサイクル $2$ つが作られることが分かります．
逆に与えられた順列を $2$ 回で作るには，各サイクルに対応する交互パスを選んだり，同じ長さのサイクル $2$ つをまとめて作れる交互サイクルを選んだりすればよいです．
$dp[\text{cycle len}][\text{cycle cnt}]$ のような dp （$O(N\log N)$ 状態）をしておけば，順列のサイクル分解からその方法の数え上げを計算できるようになります．
順列を $0$, $1$ 回で作れるかどうかも順列のサイクル分解の情報だけからわかりいます．
あとは $k$ 個の空欄に対処すればよいです．これは Bell(k) 全探索で対処できます．
