一応Easy早解きしましたがUnratedになりました。
Easy 250
問題文
本当にうろ覚えなので嘘かも。なんかある箱を使うと石を少なくともx個,最大でもy取り出さなきゃいけないという制約があって、箱の使い方は任意。 9000より大きい石を得たい。その条件下で"石の数"の組み合わせ数を数えなさい。
制約
- 箱の数n <= 10 , 1 <= x <= y <= 1,000,000
解法
9000は心底どうでもいい。まあ箱の選び方は2^10なので「ある箱の選び方」をしたときに作れる石の範囲を作ってみると、ある数の石について、それを含む区間が１つ以上あるかを数え上げるかという問題になるので、imos法などでゴニョっとやってやる。石の数の最大1500万なのでうまくやれば座標圧縮しなくても良い。
いもす法
区間の始めに+1,終わりに-1(このへんは閉/開区間どちらかでずれたりする)でして、それを元に累積和配列を作ると配列のそれぞれの添え字にはその座標をカバーしている区間の数が記録される。O(N) [N:=配列の長さ]
