Universal Cup Stage.10 (Zhejiang) A - Atcoder Problem

$O(N\log N\log M)$ と重めだが高度な fps を用いない方法。

問題概要

$n=1,2,\ldots,N$ について、以下を満たす長さ $n$ の数列 $A$ の個数を求めよ。

$0 \le A_1 \le A_2 \le \ldots \le A_n \le M$
$A_1 \oplus A_2 \oplus \ldots \oplus A_n = X$

$1 \le N \le 10^5$
$0 \le M,X < 2^{60}$

解法

$M$ に $1$ を足して、 $0 \le A_1 \le A_2 \le \ldots \le A_n < M$ と言い換えておきます。また、 $n$ の時の答えを $f_n$ と表記します。

ここで、 $0 \le B_1 < B_2 < \ldots < B_n < M$ かつ $\bigoplus_i B_i = X$ を満たす $B$ の個数を $g_n$ とおくことにして、 $F:=\sum_n f_nx^n, G:=\sum_n g_nx^n, H := \sum_i \binom{M-1+i}{i}x^{2i}$ とすると、 $F=GH$ が成り立ちます。(これは ABC288Ex の解説とかで触れられてると思います)よって、 $g_n$ を求めることができればよいです。

今後、以下が成り立つことを利用します。( $N$ が偶数の場合未証明、実験で導きました)

かつを満たすの個数をとおくと、
- $N$ が奇数の場合、 $h(X)$ は一様分布。
- $N$ が偶数の場合、 $h(X)$ は $X=0$ を除いて一様分布。また、 $h(0)-h(1)=(-1)^{N/2}\binom{2^{M-1}}{N/2}$ が成り立つ。

KUPC2017K の別解と同じように、上の桁から考察していきます。いま $k$ 桁目を見ているとします。 $M,X$ ともに $k$ 桁目が $0$ ならば $k-1$ 桁目に移ります。 $M$ のみが $0$ ならば答えは $0$ です。 $M$ の $k$ 桁目が $1$ とします。

ここで、 $B$ の $k$ 桁目について考察します。 $0$ が連続したあと $1$ が( $X$ の $k$ 桁目が $1$ なら奇数個、そうでないなら偶数個)連続する形になります。ここで、前半の $0$ が連続する部分の下の桁は $[0,2^k)$ の値を一様に取れることが重要で、もし $0$ の連続する個数が奇数ならこの時点で答えがわかります(上の桁が $1$ である部分が何であろうと関係なくなるので)。また、 $0$ の連続する個数が偶数の場合も、 XOR が $0$ である場合以外は一様ですから、一様として答えを求めた後、 $0$ の長さを $2t$ として、 $(n-2t,M \bmod 2^k, X \bmod 2^k)$ についての問題の答えを用いて「補正」をしてあげればよいです。ここで、持つべき必要がある状態を考えると、「 $g_{k,n}:=(n,M\bmod 2^k,X\bmod 2^k)$ の時の答え」のみであり、 $k$ が小さいほうから計算していくことができます。状態遷移が畳み込みの形になっていることに気を付けると、 $O(N\log N\log M)$ でこの問題が解けます。