線形解法がおもったより単純だった 解法 (swap数の総和) (完全順列の数) を求める問題である 個の要素の完全順列の数 とすると，これは有名らしく， で線形で求まる． swap数は に辺を貼った時の サイクル長 だけかかる サイクル長 となる，要素の選び方が …

問題リンク 解説 問題文をまず言い換えます。 をするということはその辺のコストをにすることで、 をすることはその辺を2倍することと言い換えることができます。 そして、じゃない辺でやると得をしないので、任意の辺でどこのコストを0にしてどこのコストを…

MP法を用いて、goalの前 文字に文字 を加えた文字列のsuffixがgoalのprefixと何文字一致するかを前計算します。 後のDPは簡単で、計算量は です 追記(DPパート) 簡単でで説明を省略しない！ということで簡単に スタートから に行くまでの期待値 とします。 …

問題リンク 解説 中学1年生になりましょう です。 欲しいのは としたときの でこれは↑の式を適宜modを取っていきながら繰り返し二乗法で展開すれば、計算量は です 提出コード atcoder.jp

問題リンク 解説 年齢が若い順に見ていきます。 すると、それぞれの辺を加えるか削除するかがわかり、各頂点の左端と右端がわかります。 この更新は遅延セグ木や双対セグ木を用いて、 でできるので解けました。 提出コード atcoder.jp

問題リンク 解説 前計算である集合が条件をみたすかを前計算します。 これは愚直にでできます あとは をすでに分ける最小の数 とすると、これは部分集合を列挙するテクを用いてでできます。 以上で求めることができました。 提出コード Submission #19137551…