無限級数
コンテスト中には通しきれなかった。流石に疲れていて頭が働かなかった......これはメモ代わりに記す。 問題へのリンク 問題概要 整数値 が等確率で出てくるルーレットがある。 先手と後手が交互にルーレットを回す すべての整数値が揃ったら終了である すで…
Codeforces
数え上げ問題
期待値
期待値DP
テク:K以上からK+1以上を引く
主客転倒
約数系包除
最大公約数
条件の言い換え
包除原理
式変形
無限級数
エラトステネスの篩
回数の期待値
高速メビウス変換
CodeforcesDIV2
CodeforcesR2300
メビウス関数
これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …
自己ループを除く
期待値
期待値DP
DP
包除原理
bitDP
累積和
DP高速化
DP高速化:累積和
高速ゼータ変換
主客転倒
テク:K以上からK+1以上を引く
O(3^N)
TopCoder
SRMDIV1Medium
無限級数
回数の期待値
楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…