被覆する方法の数え上げ
こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…
AtCoder
AtCoder700点
企業コン
数え上げ問題
DP
包除原理
ナップサックDP
二項係数
区間
操作
区間操作
被覆する方法の数え上げ
重複を防ぐ場合分けのテクニック
上書き操作
補集合を考える
区間に関する各条件を満たすものの個数
700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…