集合冪級数(SPS)
AtCoder
AtCoder600点
橙色diff
ABC-G
除原理
数え上げ問題
高度典型
主客転倒
個別の要素の動きに注目する
指数探索系問題
DP
bitDP
O(3^N)
O(3^N)なbitDP
SubsetConvolution
集合冪級数(SPS)
SPSテク:f=log(exp(f))
解空間:O(N!)通りの選択肢
順列の数え上げ
グラフ
グラフ・盤面・数列の個数の数え上げ
グラフの頂点集合の部分集合を走査する
個人的要復習
期待値
期待値の線形性
線形性に着目する
連結成分
集合族に関する問題
最小添字規則によってダブルカウントを防ぐ
場合分け
除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…