ABC129 E - Sum Equals Xor

所感

0b1000 < 0b0111、言われてみれば死ぬほど当たり前なんだけど上から桁DP + 二進数で見えなくなっていたよね(言い訳)

問題概要

正整数Lが二進数表記で与えられる。
a + b <= L
a + b = a ^ b
なる(a, b)の組み合わせの個数を10⁹+7で割った余りを求めよ。

取った方針

a + b == a ^ b なるa + bを列挙して何かしらの法則性を見つけようとして死亡

正しい方針(解説の方針)

xor は繰り上がりのない二進数の足し算という情報系知識がある。
つまり、繰り上がりのない足し算(k桁目の値が両方1ではない)ならa + b == a ^ b となる。
これを考えつつ桁DPをする。(桁数が非常に多いこと、桁に関する条件があることから思いつく。)

dp1[i] := 上からi桁目まで確定していて、既にa + b < Lが確定している場合の数
dp2[i] := 上からi桁目まで確定していて、まだa + b < Lが確定していない場合の数
i桁目の時点でa + b < L が確定している ⇔
以降の値がすべて1になったとしてもa + b < Lである ⇔
i桁目までにL[k] == 1 && bin(a + b)[k] (binは数を受け取って二進数文字列を返す関数)なるkが存在するであることに気を付けて遷移を考えると、遷移はイカになる。i桁目を0にするには(0, 0)の1通り、1にするには(0, 1), (1, 1)の2通りがあることに気を付ける。

if (s[i] == '1') {
    //既にa+b<Lの場合は任意
    dp1[i] += dp1[i - 1] * 3;
    //a+bを0にする
    //Lのi番目が1でa+bのi番目が0のとき、 a + b < L  が確定する
    dp1[i] += dp2[i - 1];
    //1にする
    dp2[i] += dp2[i - 1] * 2;
}
else {
    //既にa+b<Lの場合は任意
    dp1[i] += dp1[i - 1] * 3;
    //a+bを0にするしかない
    dp2[i] += dp2[i - 1];
}

得られた知見

・桁数が大きい + 桁に関する条件 =>桁DP
・xor は繰り上がりのない二進数の足し算
・桁DP に詳しい記事:

drken1215.hatenablog.com

解くのに必要な要素

・xor は繰り上がりのない二進数の足し算(知識)
・桁 DP ・桁 DP に関連して、xの中身が何であったとしても8000 > 7xxx であるという当たり前の感覚

周辺調査によって得られた知見

特になし

ymduu+2

初心を忘れないのでツンデレとPSPが今でも好き、技術メモとか制作物とかそういうの