ARC 066 D - Xor Sum (600) - くるのプログラミング記録

皆大好きXor Sum。解き直したので。
リンク：D - Xor Sum

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

問題文

正の整数 $N$ が与えられます。
2 つの整数 $u,v (0 \leq u, v \leq N)$ であって、ある非負整数 $a,b$ が存在して、 $a\ xor\ b = u, a + b = v$ となるようなものが何通りあるかを求めてください。ここで、 $xor$ はビットごとの排他的論理和を表します。なお、答えは非常に大きくなることがあるので、 $10^{9}+7$ で割った余りを求めてください。

制約

$1 \leq N \leq 10^{18}$

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

難しい。 $N$ が大きすぎて何もできない。
最終的には $O(\log{N})$ になるんだけどその解説も天才すぎる。
https://atcoder.jp/img/arc066/editorial.pdf

桁dpということを強く意識して解いてみる(結局やることは解説まんま)

解説前半部分の $a + b \leq N$ だけ考えれば十分って部分は典型なのかな。

基本情報技術者の勉強で半加算器とか見てると分かりそうな気もする。

結局問題としては $a + b \leq N$ を満たす $a,b$ の組み合わせの数の桁dp(正確にはbit桁dpかな)

まず $N$ を2進に直す(bitsetとかvector < bool > とか)

$10^{3} \leq 2^{10}$ なので $10^{18} \leq 2^{60}$ 、60桁あれば十分。
　

桁dpなので上の桁から決めていく。解説通りにdpをとる。

「 $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}=a$ と $b$ の $i$ ビット目以上が決定していて、その段階で $(v >> i) = (N >> i) - j$ となる通り数。」

最初何言ってるか分からなかった。天才過ぎて辛い。
具体的にやることは $N$ のビットを上から見て、それ以下になるような数を数え上げる。
(普通の桁dpと同じで、上位の桁がある程度決まると下位の桁をどうとっても $N$ 以下になるという性質を利用する)

dpテーブルは $dp\begin{bmatrix}61\end{bmatrix}\begin{bmatrix}3\end{bmatrix}$ ととり(0-indexed)、初期化は $dp\begin{bmatrix}60\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$ それ以外は $0$ 。
(この $dp\begin{bmatrix}60\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$ というのは $N$ の60桁目のビット(0-indexed,また制約より必ず0)に対して $a,b$ の60桁目のビット(0-indexed)をともに $0$ ととることで必ず題意を満たすことができるので)(簡単に言うと $0+0=0$ )(それはそう)

まず先にコードを書くとこんな感じ。

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7; 

int main() {
	ll N; cin >> N;
	bitset<60> bs(N);	//2進に直す
	vector<vector<long long>> dp(61, vector<long long>(3, 0));//dpテーブル
	dp[60][0] = 1;//初期化
		
	//上の桁から見ていく
	for (int i = 59; i >= 0; --i) {
		//i桁目のbitが立ってるとき
		if (bs[i]) {
			dp[i][0] = dp[i + 1][0];
			dp[i][1] = dp[i + 1][0] + dp[i + 1][1];
			dp[i][2] = 2 * dp[i + 1][1] + 3 * dp[i + 1][2];
		}
		//i桁目のbitが立ってないとき
		else {
			dp[i][0] = dp[i + 1][0] + dp[i + 1][1];
			dp[i][1] = dp[i + 1][1];
			dp[i][2] = dp[i + 1][1] + 3 * dp[i + 1][2];
		}
		dp[i][0] %= MOD;
		dp[i][1] %= MOD;
		dp[i][2] %= MOD;
	}
	cout << (((dp[0][0] + dp[0][1]) % MOD) + dp[0][2]) % MOD << endl;
	return 0;
}

$N$ のビットを上から見ていく(for int i = 59; 0 <= i; --i)

イメージとしてはこんな感じ。
f:id:ningenMe:20180911183219p:plain
(今この $N$ は適当な $N$ )

このとき $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ が何を表しているかというと
「 $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}=a$ と $b$ の $i$ ビット目以上が決定していて、その段階で $(v >> i) = (N >> i) - j$ となる通り数。」である。ここが一番分かりにくい気がする。

$N$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $M_i$ 、
$a$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $\alpha_i$ 、
$b$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $\beta_i$ として見たとき

$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_i+\beta_i=M_i$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_i+\beta_i=M_i - 1$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_i+\beta_i \leq M_i - 2$ となる通り数。である(これでも分かりにくいけど)

f:id:ningenMe:20180911185005p:plain

ここで次のビットである $i-1$ 桁目を考えると
$N$ の $i-1$ 桁目が $1$ のとき $M_{i-1}=2M_i + 1$ 、
$N$ の $i-1$ 桁目が $0$ のとき $M_{i-1}=2M_i$
となる(2進数の定義より)

場合分けして丁寧に遷移を考える。

(1) $N$ の $i-1$ 桁目が $1$ のとき

$M_{i-1}=2M_i + 1$ より $dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ について以下のようになる。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1}=2M_i + 1$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1} - 1=2M_i$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1} \leq M_{i-1} - 2 = 2M_i - 1$ となる通り数。

ここで
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_i+\beta_i=M_i$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_i+\beta_i=M_i - 1$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_i+\beta_i \leq M_i - 2$ となる通り数、だったので
$\alpha_i+\beta_i$ の遷移を考えると2倍して0 or 1 or 2を足すという操作ができる。
( $a,b$ の $i-1$ 桁目のビットについて、共に1、どちらか一方が1、共に0の高々3種類なので)

よって以下のような遷移を考えればよい。

f:id:ningenMe:20180912022255p:plain

従って
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i+1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+1$ の1通りのみで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+2$ の1通り、計2通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+0,+1$ の2通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-4)$ に対して $+0,+1,+2$ の3通り、計5通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=2dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

(2) $N$ の $i-1$ 桁目が $0$ のとき

$M_{i-1}=2M_i$ より $dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ について以下のようになる。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1}=2M_i$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1} - 1=2M_i - 1$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1} \leq M_{i-1} - 2 = 2M_i - 2$ となる通り数。

(1)と同様に以下のような遷移を考えればよい。

f:id:ningenMe:20180912022052p:plain

従って
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+2$ の1通り、計2通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i - 1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i - 2)$ に対して $+1$ の1通りのみで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-2)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-4)$ に対して $+0,+1,+2$ の3通り、計4通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

以上をまとめて
(1) $N$ の $i-1$ 桁目が $1$ のとき
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=2dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

(2) $N$ の $i-1$ 桁目が $0$ のとき
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

以上の遷移を行うことで $dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ が答えとなる。

難しすぎる。700点でしょ(800点でもいい)
ビットの遷移が $+0,+1,+2$ しかないので $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq M_i-2)$ の状態をまとめられるってのが凄い、ある意味桁dpらしいような気もするし強い人は気づくのかな。天才になりたいものです。