betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 F - Xor Sum 3 線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。 前段の考察 を表すビット桁を 桁目と表記することにします。一番下が0桁目です。 各ビット桁ごとに、 のうち 桁目が立っている要素の個数を と表記します。 が奇数である場合、2つのグループにどう分けても 桁目のビットは最終的な答えに 貢献します。 一方偶数である場合、それが奇数個ずつ分かれると答えに 足され、偶数個ずつ分かれると答えには何も足されません。 よって前段の考察は以下のようになります。 が奇数である桁について を合計したものを求めておき、これを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F11%2F22%2F012255" title="AtCoder Beginner Contest 141 F - Xor Sum 3 - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20N Hatena Blog https://hatena.blog 2019-11-22 01:22:55 rich https://betrue12.hateblo.jp/entry/2019/11/22/012255 1.0 100%