baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ bit 探索範囲を削る D - Two Sequences 長さNの数列 a,bが与えられる。 ai bjのN^2の全ての選び方について、ai + bjを計算しする。 それらのxorを求めよ 制約 入力は全て整数 1≤N≤200,0001≤N≤200,000 0≤ai,bi<228 解法 愚直に計算すると間に合わない。 xorは繰り上がりしないので、ある桁で1が奇数回足されればその桁は1になる。 0から数えてK桁目について考える。 ai bjを足した時、K桁目が1になるのはどんな条件の時だろうか？2 ^ KをTとすると、合計がTの時はK桁目だけが1になることが分かる。K桁目が繰り上がるまでは条件を満たす。具体的には[… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2018%2F07%2F09%2F193455" title="D - Two Sequences　AtCoder Regular Contest 092　 - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-07-09 19:34:55 rich https://baitop.hatenadiary.jp/entry/2018/07/09/193455 1.0 100%