A. Passing the Ball
そのままシミュレーション．
B. Right Maximum
適当なタイブレイクに注意して，prefix から見て max になっているところを数えます．
C. Spring
$8$ 通りの状態について上位集合メビウス変換．
D. Alternating Path
連結成分内に奇サイクルがあると無理だと分かります．
連結成分が二部グラフであるとき，good にできる点は二部グラフの片方の部集合だと分かります．
E. Sum of Digits (and Again)
$1$ 回以上 digit sum をとったとして，$9|S|$ 以下の何かを経由します．これを全探索すれば十分高速です．
F. Sum of Fractions
まず要素数がひとつのときの操作について考えます．ありうる選択肢の中では分子分母の差が固定されているところから，調べると，次のような感じになります．
初期状態を $1/4$ としたとき
- 操作回数 $0$：$1/4$
- 操作回数 $1$：$2/4$
- 操作回数 $2$：$3/4$
- 操作回数 $3$：$4/4$
- 操作回数 $4$：$2/1$
- 操作回数 $5$：$3/1$
- 操作回数 $6$：$4/1$
- $\cdots$
操作回数 $1$ 回あたりの利得は途中までは $1/b$，途中からは $1$ となります．
それを踏まえて要素がたくさんあるときの操作について考えると，最小値に対してだけ操作をするとしてよいことが分かります．
コストの計算では，たいていの要素は $1/a_i$ のまま寄与します．$a_i$ が最小値として選ばれたときだけ補正するということになります．
$k$ に対するクエリでは，求めるものは $base + \sum_i f(k,a_i)\cdot c_i$ のような形になります．$base$ がすべてのクエリに共通の計算パート．$c_i$ は $a_i$ が最小値採用される回数です．あとは $f(k,a_i)$ について式を立てると，$a_i$ と $k+1$ の大小関係で切って適当な計算をすることになります．ソートしていくつか累積和を用意しておけばよいです．
G. Grid Path
区間の列を作って，どの隣接する $2$ つの間も交わるようにする．ということです．
なんらかの行列累乗的問題だというのは分かると思います．mod が素数ではないので，（中国剰余定理を使っても）そのまま Berlekamp-Massay は出来ないと思います（調べれば何かあるかもしれないがとりあえず出来ないということにします）．
いったん行列は忘れて，同じことですが，dp での解法を考えます．$\mathrm{dp}[L][R]$ というタイプの状態の持ち方をしてしまうと失敗なので，どう状態を持つかを考えます．実は次の $2M$ 状態で ok です．
- $\mathrm{dp}_1[i]$：最後の区間の左端が $i$ であるような方法の総数．
- $\mathrm{dp}_2[i]$：最後の区間の右端が $i$ であるような方法の総数．
定義から $\mathrm{sum}=\sum_i \mathrm{dp}_1[i] = \mathrm{dp}_2[i]$ です．初期値の問題があるため，$\mathrm{dp}_1[i]\neq \mathrm{dp}_2[M-1-i]$ です．
次の区間を $[L,R]$ とする方法はこれらから計算できます．$\mathrm{sum}$ から引いていくとすればよいです．これを計算して $\mathrm{newdp}_1[L], \mathrm{newdp}_2[R]$ に足すという要領で dp が完成します．
これに，パスをその行まででストップするという状態を追加して，$(2M+1)$ の大きさの行列で解くことができます．
