F - Tree and Constraints
__builtin_popcountll
解説ACをしていきたい
説明
流れ
まず、条件を満たすものの数え上げ…ではなく「全ての通り - 条件を満たさないもの」というふうにして、条件を満たさないものを数えていくことにする
「区間中のどれかが塗られていたらOK」、は扱いにくいので「区間中の全てが塗られていない」を引く、という方針で考えることにします…
包除原理をする
解ける
包除原理、どうやって実装するねん
今回何を求めたいのか?→全ての制約を満たすものの個数
全ての通り数 - どれかの制約を満たさないものの個数 で求めることが出来ます
https://gyazo.com/df3d152df61bae898f5044977dc5f0a7