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; }