級数和を求める
まさに遅延評価セグメント木の練習問題!!! 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…
AtCoder
AtCoder900点
ARC-like
数え上げ問題
期待値
期待値の線型性
順列
操作
K回操作後の結果を求める
個別の要素の動きに注目する
縦に見るものを横に見る
転倒数
BIT
級数和を求める
データ構造
シャッフル
差分更新
f(i,j)をiとjとに分離する
橙色diff
コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…
AtCoder
AtCoder400点
ABC-D
DP
DP高速化
DP高速化:累積和
累積和
いもす法
DP高速化:いもす法
数え上げ問題
部分和
多項式・形式的冪級数
級数和を求める
形式的冪級数の高等演算
水色diff
DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした!) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …
AtCoder
AtCoder600点
ABC-F
特殊なmod
行列
行列累乗
総和を求める
多項式・形式的冪級数
各桁ごとに見る
級数和を求める
整数値のconcatを考える問題
縦に見るものを横に見る
個別の要素の動きに注目する
橙色diff
重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…