読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

8VC Venture Cup 2016 - Final Round (Div. 1) B. XOR Equation

動的計画法

何も考えず桁 DP したけど結果的に提出は早かったので良しとしたい。

codeforces.com

問題概要

和が s、xor が x になるような正整数の対 (a, b) はいくつあるか。

解法

s, x を二進数になおしてから桁 DP。

  • dp[ 下 i 桁まで処理済み ][ 桁上りがある ] := この状態に至るパターン数

下の桁から条件に矛盾しないように決めていけば良い。s=x のときに (s, 0),(0, s) を数え上げないように注意。

Submission #16423185 - Codeforces

8VC Venture Cup 2016 - Final Round (Div. 1) B. XOR ...

最近桁 DP で解ける問題出すぎでは…。