■いわゆる包除原理 N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち 2乗のDPになりがち■min・max 期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にある…

これを読解した Submission #27805654 - AtCoder Beginner Contest 220参考にしたツイートこれやっと読解できた気がする適切に行列作ると求めたいものは二次形式の値が偶数になるような01ベクトルの個数になる問題の性質から作れる操作と直交変換かますこと…

この記事を書いた4時間後に以下の記事が公開されました。これを読もうね－完－ maspypy.com以上で本質情報は終了です。ありがとうございました。以下はおまけです。 まえがき この記事を読んでも競プロに強くはなれませんよ。 FFTで多項式乗算が高速にできる…

期待値= というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。 問題： S+1の状態があり、状態0から始めて、状態Sに到達したら終了。 1回の操作で状態iから状態jに遷移する確率がのとき、終了…

というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。記号 メビウス関数 命題Pに対してをPが真なら1、偽なら0とする（アイバーソンの記法 - Wikipedia） やりたいこと がある。を求める。 例…

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。FPSパワーを感じる学びがあったのでまとめる。出典「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は になる。 したがって、「全ての…

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。 オリジナル：Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） 数列 に対して、終了条件を満たすまでの操作回数の期待値…

これの続き sugarknri.hatenablog.com201 DP202 前座パートは中受典型 No.306 さいたま2008 - yukicoder 本編前半は3種類の直線をZ[ω]座標系で書いて考える 本編後半は素因数分解してDPなり包除原理なり203 やるだけ クンマーの定理を思い出してもいい204 O(…

これの続き sugarknri.hatenablog.com「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。151 DP152 1/kpを使ったら、pがどこかで約分される必要があります バックトラックDFSで全探索 指数でも分…

これの続き sugarknri.hatenablog.com101 ラグランジュ補間 普通にやるとO(N^3) 補間に使う点が等差数列なのでO(N^2)にできる ラグランジュ補間したときの係数をぐっと睨むと求めるものをexplicitにも書ける102 多角形の内外判定 普通は半直線と線分の交差判…

これの続き sugarknri.hatenablog.com51 3の倍数で枝刈り52 有名問題すぎる53 尺取 rが小さいうちは境界を直接計算すると早い54 気合55 多倍長整数56 多倍長整数 嘘下界を使って嘘枝刈りで高速化57 連分数の最後に1項増やしたときの挙動を知っていますか 分…

間違ってたりより良い解法があったら教えて計算量は四則計算の回数。桁が増えすぎると壊れる 1 包除原理 これくらい手で解け2 愚直で解ける 項数を先に求めて行列累乗すればO(loglogN) 一般項を出して適当なmodを取ってCRTすると実質O(1)3 素因数分解の計算…

これを読め rsm9.hatenablog.com ～終わり～ 以下ポエム ひとなのでさんによるこの記事を読むまでbeatsの理解が困難だったが、この記事を読むと全てを3秒で理解できた。 これ以前に存在していた記事で理解が困難だったのは、まずそもそもbeatsというデータ構…

bit毎の排他的論理和を 、論理積を と置くと、 任意の非負整数 に対して が成り立ちます。 これは を観察すれば成り立つことが示せます。 この等式は競技プログラミングで非常によく使われるテクニックの一つです。 Yukiちゃんはこの等式を一般化して、 の形…