平方分割でも解けたので紹介しようかなと。 問題 s8pc-2.contest.atcoder.jp 解法 bit[i] = (i 番目の bit がどうなっているか) flag[i] = ([i*B, (i+1)*B) 番目の bit は bit[i] から反転させたものになっているか, cnt[i] = ([i*B, (i+1)*B) で立っている …

問題 s8pc-2.contest.atcoder.jp 解法 遅延評価セグメント木で解きました。update で [l, r) の区間を反転させ, query で [l, r) の 1 の数を求めるような機能を実現します。lazy 配列には「今考えている区間は後で反転させるつもりか」というのを覚えておき…

問題 s8pc-2.contest.atcoder.jp 解法 なんか調べると b^(a-1-i) に掛け算される係数は 1/i! * c*(c+1)*...*(c+i) になります。なのでそれを実装すれば OK です。調べ方ですが, b^3 あたりの列を調べると, b^0 の項が 1, 4, 10, ... となっています。b^2 で…

面白かったです。 問題 s8pc-2.contest.atcoder.jp 解法 「どの数で割られるか」で 2^q の場合分けをします。i1, i2, ..., im 番目の数で割られて 1 になる場合, 元の数は q[i1] * a[i2] * ... * a[im] です。 これが本当に i1, i2, ..., im でのみ割られる…

問題 s8pc-2.contest.atcoder.jp 解法 「約数 多い」で調べると, 高度合成数という言葉が出てきます。 高度合成数 - Wikipedia結局この問題ではこれを求めろ, ということなのですが, 高度合成数には次のような特徴があるようです。高度合成数は という形で素…

問題 jag2016-domestic.contest.atcoder.jp 解法 候補になる直線は, 有権者と障害物の頂点を結んだ直線ですが, これを何本も引くことを考えると結局考えるべき頂点は「有権者と障害物の頂点を結んだ直線」同士の交点であることがわかります。この点を列挙し…