A. Nim Game Is XOR Game
$1$ 手で勝てるだろうと予想して考えました．
- 正の山が $1$ 個以下だと負け．
- 正の山が $2$ 個以上だと勝ち：残す正の山を $1$ 個以下にできる．
なぜならば，全体 XOR が $0$ ならば全部とればよい．そうでなければ，NIM のプレイでとるときの個数を逆に残すようにする手があります．
これで勝利条件は分かりました．すると数え上げは，正の山が $1$ 個以下になるように手を打つ方法の個数です．
B. Decidophobia
$\pm 1$ 列を決めた上で，$\sum (x_i-x_j)a_i$ のようなスコアになります．これを $x_i$ ごとに整理して，$\sum c_ix_i$ のような形にして項ごとに独立に最適化すればよいです．
C. Revival
後ろから決めていくことができます．だいたいどうなっているかというと，前回 inv が与えられた場所から数えて
$\ldots,?,a,b,c,x$
のようになっています．$a,b,c,x$ を追加したときの inversion 増加量が分かっているし，（末尾から一意に確定しているという前提で）列のこの部分にある数全体も分かっています．
重要なのは，$x$ を決めるとここの部分の inversion 増加量が計算できることです．しかも，$x$ について単調になるので二分探索できます．
D. Hunting the Beast
大変解法になってしまった．2 変数 FPS をします．共通の前提として，
- $x$ の指数は頂点数に対応
- $y$ の指数は始点集合採用した頂点数に対応
- $x$ については EGF で $y$ については OGF，つまり数え上げを $a_{n,m}$ として $\sum \frac{1}{n!}a_{n,m}x^ny^m$ の形
とします．
- 根付き木であって葉はすべて始点集合採用しているもの：$A(x,y)$
- 根付き木であって，根以外の葉はすべて始点集合採用しているもの：$B(x,y)$
- 問題の条件を満たす連結 functional：$C(x,y)$
- 問題の条件を満たす functional：$D(x,y)$
とします．
- $A = B-x$：$1$ 頂点の木の場合の補正
- $B = (x+xy)e ^ A$：根を採用するのが $xy$ で採用しないのが $x$
- $C = \sum_{k\geq 2}\dfrac{B^k}{k}-\sum_{k\geq 2}\dfrac{x^k}{k}$：$B$ をサイクル状に並べる感じ．loop がないので $k\geq 2$ としている．全部 $1$ 頂点で不採用にした場合についての補正を引いている．
- $D = \exp C$：いつもの．
結局整理すると，
- $B = (x+xy)e ^ {B + x}$ のときに
- $[x^ny^m]\dfrac{e^x(1-x)}{e^B(1-B)}$ を求めよ
ということになります．
前者の式は，$B = xe^x(1+y)e^B$ とします．こんなの扱えないという気がしたのですが，よく考えると，$B=T(xe^x(1+y))$ です．$T$ は $T = xe^T$ を満たすいつものです（ラベル付き根付き木の EGF）．
まず
$$\frac{1}{e^{T(x)}(1-T(x))}=\sum a_kx^k$$
となる係数 $a_k$ を求めます．すると求めるものは
$$\sum_k a_k \cdot [x^ny^m] e^x(1-x) (xe ^ x(1+y)) ^ k$$
となって，答が $O(n\log n)$ くらいで求まる感じになっています．$a_k$ ははじめ合成で求めたのですが，$10^6$ 制約だと遅かったので，実験して当てはめました（ラグ反すれば分かりますが）．
E. The end of this world
まだ
F. Colorful Works
まだ
