pekempey's blog

998244853

ABC129 E. Sum Equals Xor

https://atcoder.jp/contests/abc129/tasks/abc129_e

I solved it by digit DP with ordering monoid. In this DP, we scan the digits from the lowest to the highest as maintaining (order, carry). Iwarete mireba a+b=(a^b)+2*(a&b) kizuku beki.

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
  return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
  int x = a.n + b.n;
  return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
  int x = a.n - b.n;
  return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
  return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

mint dp[100003][3][2]; // EQ, LT, GT

enum { EQ, LT, GT };

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  const int n = s.size();
  dp[n][EQ][0] = 1;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 2; k++) {
        for (int x = 0; x < 2; x++) {
          for (int y = 0; y < 2; y++) {
            int v = x + y + k;
            int u = v % 2;
            if ((x ^ y) != v % 2) continue;
            int nj = j;
            if (s[i] - '0' < u) nj = GT;
            if (s[i] - '0' > u) nj = LT;
            dp[i][nj][v / 2] += dp[i + 1][j][k];
          }
        }
      }
    }
  }
  cout << dp[0][LT][0] + dp[0][EQ][0] << endl;
}