-
Notifications
You must be signed in to change notification settings - Fork 0
Memo
ビット
a+b = a^b + 2*(a&b)この関係から、
(a+b+c+...+z) = (a^b^c^...^z)
が成り立つ条件として、bit上の全ての桁について
a..zの中で1が立っているものが1個以下であると言える。
また、
xorとandは半環であるので
xor-> + ,and -> x
の要領で見ることができる
https://beta.atcoder.jp/contests/abc009/tasks/abc009_4ではこの性質を用いて行列累乗を行う
組み合わせ
1以上N以下のN個の整数の中から相異なるK個の整数を選び，順番に並べるパターンの数P(N,K)
N!/(N-K)!
1以上N以下のN個の整数の中から重複を許してK個の整数を選ぶパターンの数H(N,K)
C(H+K-1,K)
但し、N = K = 0のとき例外で 1
最小公倍数と最大値
ある値B以下のAからスタートして、Dずつ足していく時、個数 mod Bの最大値は
g=gcd(B,D)として B-g+(A mod g)となる。
また、 (B/g-1)*inv(D/g,B/g)回Dを足したときに達成できる。
ここで、inv(X,Y)は、X * inv = 1 mod Yとなる値。
これを使う問題 : https://atcoder.jp/contests/agc026/tasks/agc026_b
対応が取れている文字列とは
((()))() や ()()(())みたいなやつ
これは
・'('と')'が同じ回数登場する
・文字列の途中までを見たとき'('の登場する回数が')'の登場する回数以上
の２条件を満たすことと等しい
連結成分が木となる時
木が与えられた時
・頂点数 = 辺の本数+1
森が与えられた時
・頂点数 = 辺の本数+連結成分(木)の個数
https://ei1333.github.io/luzhiled/snippets/memo/project-selection.html
https://www.slideshare.net/shindannin/project-selection-problem
http://yosupo.hatenablog.com/entry/2015/03/31/134336
https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow/burn_bury_problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2903