ARC 066 D - Xor Sum

• 問題

問題概要

自然数Nが与えられる.
0 <= u,v <= N であってa+b <= u, a^b <= v を満たす非負整数a,bが存在するようなu,vのペアはいくつあるか.
1 <= N <= 10¹⁸

解法

a+b = ( (a & b) << 1 ) + (a ^ b)であることから,a+b >= a ^ b.
また, a&b = ( (a+b) - ( a ^ b ))>>1 から, u, vを決めると a ^ b, a&bが決まる.
(a^b, a&b) = (0,0),(1,0),(0,1) に対して((1,1)はありえない),
(a, b) = (0,0), (1,0), (1,1) とすれば, a ^ b, a&bからa,bは1通りに決まる.
すなわちa,bをビットの集合とみた時 a ⊇ b ということに相当する.
よって, a+b <= N, a ^ b <= N, a⊇b を満たす a,b のペアの数を求めれば良い.

a+b = S, a^b = X を満たすa,b の数を f(S,X) とすると,
a,b の最下位ビットが(0,0),(1,0),(1,1)の各場合に分けて,
(0,0) -> f(S/2,X/2)
(1,0) -> f((S-1)/2, (X-1)/2)
(1,1) -> f(S/2-1,X/2)
だが結局常に X <= S なので, S = X = n として,
f(n) = f(n/2) + f((n-1)/2) + f(n/2-1)
これをメモ化して求めれば良い.

メモ

解説は上から決めていく桁DPだった.
そのうちそっちでもやりたい.

あと OEISで検索するという知見を得た.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 1003;

int main(){
  ll N; cin >> N;
  map<ll,ll> mp;
  mp[0] = 1LL; mp[1] = 2LL;
  function<ll(ll)> solve = [&](ll n){
    if(mp.count(n)) return mp[n];
    return mp[n] = (solve(n/2) + solve((n-1)/2) + solve(n/2-1)) % lmod;
  };
  cout << solve(N) << endl;
  return 0;
}