メモ

知らなかったできることのメモとか

1e18+3(codeではll 1LLe18+3)は素数
inv(1e9+7) mod(1<<64) = 13499267949257065399ULL ←これよく考えたら普通にオーバーフローさせながら計算すればよかった
DAGにpathを何個書けば頂点が覆えるか->bipartite matching
和がnになるような1以上の整数達がいる時、種類は√2nくらい (よく考えたら自明だった)
負辺min_cost_flowははじめのポテンシャルだけBellmanFord
木DPでstackoverflow->先にbfsでtopological orderをとる
二人ゲームで手番数が決まっていて相手の手をキャンセルできる手が打てる場合のmin-maxは手番数kとするとk=1,2しか考えなくて良い
挿入,削除ありのk番目の値→setで先頭k個を持つ
Z-algorithmでs[i~]とTのpfx が全部求められる
1文字違い→前からの一致+後ろからの一致=N-1
stack→区間DP
幾何で角度区間のマージ←ベクトルでやると楽かも(ただしもとより180度以上ずれてるとまずそう)
n次関数を足す→差分を取る(BITのあれみたいなのもあるけど,そもそも持つ値を差分にする も有用)
平面上4方向は45度回転で独立なx+y軸,x-y軸になる
数列で大小関係みたいな問題は平面上の点だと思うことが多い そうじゃなくてもdpとかを視覚的に表す方法があるならそれを考えるのもあり(というか図形に落として考えるのが苦手すぎる)(ex.LIS)
tの上限が1e9とかで答えがtの多項式であることがわかってるなら,小さいtについて求めて多項式補間もありうる(数え上げで結構ありそう)(わかんなければ実験も良さそう)
全部がうまく行ってるか みたいなのをクエリごとにはやく判定するためには,何個うまく行っているかを持って更新する 例えば後退解析とかでも,そこに行ける状態の内何個を処理したか を持っておき,それが全部になったらやる、みたいな
DPをデータ構造で高速化するのは貰うDPがいい(範囲のsumやmaxを一気に取りたいんだから).
dp[i]からdp[i+1]への遷移を何も考えずにsegtreeに載せると、区間を意識しなおさなくても連続部分列に対するクエリに応えられる.
連続なものはとりあえず離散的な数え上げ+簡単な積分 に落とす,たとえば∫max(a,min(b,c)) みたいなのはa,b,cの大小関係を決めたものをすべて考える.
こうするとuniform distribution[0,1]からN個独立に取ってきた時のi番目(1-indexed)の値の期待値は? になって、式を描くとベータ関数になることがわかりi/(N+1)になる. (i+1番目)-(i番目) がiによらないので1/(N+1)になることを考えるとわかりやすい.
遷移する順番が関係ないDP→
なんらかの順序でソートすると一部のキーを消せることが多い.あとcount系なら戻せる.
あとこれは最短路問題に落とせて、例えば常にコスト1でbfsになるなら計算量は変わらない.
しかし、「状態を一部に制限しても最短経路が存在する」しかしdpの順としてはこのようなものを実現するうまい順は存在しない,というような状況だと、bfsの方が計算量が良くなる場合がある.
ex:絶対値がK以下の整数がある、何個足せば0にできますか→DPだとO(K^2)状態になるが、bfsだとO(K)状態.