ABC129 E問題：Sum Equals Xor

問題. Sum Equals Xor

正整数 が二進表記で与えられる．次の条件を満たす非負整数の対 がいくつあるか求めよ．
　・
　・

制約： （ の先頭文字は必ず 1 ）

解法1

2番目の条件である となるための必要十分条件は となることである（ビットごとの排他的論理和の性質 - 忘れても大丈夫）．
したがって， 以下の非負整数 に対して， を二進表記をしたときの立っているビット数を としたとき，2番目の条件である を満たす非負整数の対 の数は である．これは， の二進表記と集合表記を対応させたときの の表す集合の分割の仕方の数と等しい．

のビット長を とする． のビットが立っている上位ビットから 番目（ 0-indexed ）に対して， より上位ビットは と等しく， ビット目は となる非負整数を考える．このとき， より下位ビットがどのようになっていても必ず 以下となる．また， より下位ビットで 1 が立っているビット数が となる非負整数の数は となる．したがって， ビット目より上位ビットで 1 が立っているビット数を とすると，条件を満たす非負整数の対の数は
　　
となる．最後の変形は二項定理による．

のビットが立っている場所に対して上の値を計算して，その総和と 2 の のビットが立っているビット数乗の和が答えとなる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    constexpr ll MOD = 1e9 + 7;

    string L;
    cin >> L;

    const int len = L.size();
    vector<ll> pow2(len + 1), pow3(len + 1);
    pow2[0] = pow3[0] = 1;
    for (int i = 1; i <= len; ++i) {
        (pow2[i] = 2 * pow2[i - 1]) %= MOD;
        (pow3[i] = 3 * pow3[i - 1]) %= MOD;
    }

    ll num = pow2[count(L.begin(), L.end(), '1')];
    for (int i = 0, sum_bit = 0; i < len; ++i) {
        if (L[i] == '0') continue;
        (num += (pow3[len - i - 1] * pow2[sum_bit]) % MOD) %= MOD;
        ++sum_bit;
    }

    cout << num << endl;

    return 0;
}

　

解法2．動的計画法

解説 にある桁DPで実装した．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    constexpr ll MOD = 1e9 + 7;

    string L;
    cin >> L;

    const int len = L.size();
    vector<ll> dp1(len + 1), dp2(len + 1);
    dp2[0] = 1;

    for (int i = 0; i < len; ++i) {
        if (L[i] == '0') {
            (dp1[i + 1] = 3 * dp1[i]) %= MOD;
            dp2[i + 1] = dp2[i];
        }
        else {
            (dp1[i + 1] = 3 * dp1[i] + dp2[i]) %= MOD;
            (dp2[i + 1] = 2 * dp2[i]) %= MOD;
        }
    }

    cout << (dp1[len] + dp2[len]) % MOD << endl;

    return 0;
}

　

自力で解けたので満足して順位表を見ると625名も解けている．上位陣がたくさんは参加していないことを考えるとレベルが高くなっている．どうしよう．