問題
正整数 $N$ が与えられるので、$\{0, 1, \dots, N\}$ の空でない部分集合 $S$ であって、$\mathrm{MEX}(S) = \mathrm{XOR}(S)$ を満たすものの場合の数を $998244353$ で割ったあまりを求めてください。
制約
$1\leq$ テストケース数 $\leq 100$
$1\leq N \leq 10^{9}$
目標
公式解説 には時間計算量 $O(\log^{3}(N))$ で解けると書いてありますが、実際には $\Theta(\log(N))$ で解くことができます。このブログでは、$\Theta(\log^{2}(N))$ で解く方法を記します。
解説
任意の整数 $x$ について、$\mathrm{MEX}(S) = \mathrm{XOR}(S) = x$ を満たす $S$ が何通りかを計算します。$x = N + 1$ のときは、$N$ を $4$ で割ったあまりが $2$ か否かで決まります。
$0\leq x\leq N$ のときは、以下の条件を満たしていれば $S$ が少なくとも $1$ つ存在します。
- $A = \lfloor\frac{N + 1}{4}\rfloor\cdot 4$ としたとき、$x< A$ が成り立つ。
詳しくは説明しませんが、任意の正整数 $a$ に対して$\mathrm{XOR}(\{0, 1, \dots, 4a - 1\}) = 0$ であることから、 $x< 4a$ であるとき $T = \{0, 1, \dots, 4a - 1\} \setminus \{x\}$ とすると、$\mathrm{XOR}(T) = \mathrm{MEX}(T) = x$ がなりたつことから示せます。
$x< A$ を満たす $x$ に対して、$\mathrm{MEX}(S) = \mathrm{XOR}(S) = x$ を満たす $S$ は何通りあるかというと、以下のようにして求めれられます。
- $\{x + 1, x + 2, \dots , N\}$ の xor に関する空間の基底の個数を $b$ としたとき、$2^{N - x - b}$ 通り
$x = 0$ のときは $S$ が空のときがあるので、注意します。$b$ の値が変わらない区間に対する $2^{N - x - b}$ の総和は、等比数列の総和なので、簡単な式になります。よって、$b$ が変化するタイミングが全てわかれば良いです。結局以下の問題に帰着されました。
サブ問題 1
$0\leq x\leq N$ を満たす整数 $x$ であって、以下の条件を満たすものを列挙してください。
- $\{x + 1, x + 2, \dots , N\}$ の部分集合 $S$ であって、$\mathrm{XOR}(S) = x$ を満たすものが存在しない。
この問題はさらに以下の問題と同値です。
サブ問題 2
$f(x)$ を以下のように定義します。
- 「$\{x + 1, x + 2, \dots , A\}$ の部分集合 $S$ であって、$\mathrm{XOR}(S) = x$ を満たすものが存在しない。」を満たす、最大の整数 $A$
$0\leq x\leq N$ を満たす整数 $x$ であって、$N \leq f(x)$ を満たすものを列挙してください。
サブ問題 2 解説
この $f(x)$ に関して、以下が成り立ちます。
- 正整数 $a$ を用いて、$x = 2^{a} - 1$ と表せるとき、$f(x) = 3\cdot 2^{a - 1} - 1$
- 正整数 $a, b$ を用いて、$x = 2^{a}b+(2^{a - 1} - 1)$ と表せるとき、$f(x) = x + 2^{a}$
$x = 2^{a} - 1$ のとき
以下のように $y, z$ を定めます。
x = 111...11 y = 1011...11 z = 1100...00
すると、$x = \mathrm{XOR}(\{y, z\})$ がなりたつので、 $f(x) < z$ です。また、$x$ より大きくて、$2^{a - 1}$ の位が $1$ になる最小の整数が $z$ であることから、$z - 1\leq f(x)$ です。よって、$f(x) = z - 1$ です。
$x = 2^{a}b+(2^{a - 1} - 1)$ のとき
$x$ を $2$ 進数表記すると、下に $1$ が $(a - 1)$ 個続いたあと、$0$ がくるような形になります。
以下のように $w, y, z$ を定めます。
x = b + 011...11 w = b + 100...00 y = succ(b) + 011...11 z = succ(b) + 100...00
すると、$x = \mathrm{XOR}(\{w, y, z\})$ がなりたつので、 $f(x) < z$ です。$x < c < z$ を満たす整数 $c$ は以下のように表せる $c1, c2$ に限ります。
c1 = b + 1??...?? c2 = succ(b) + 0??...??
$2^{a - 1}$ の位のことを考えると、$c1$ のように表せるものは偶数個しか採用できません。よって、$x < c < z$ を満たす整数 $c$ の集合の部分集合をとったものの $\mathrm{XOR}$ は $2^{a}$ で割った商が $0$ もしくは $\mathrm{succ}(b)$ に限ることから $z - 1\leq f(x)$ です。よって、$f(x) = z - 1$ です。
まとめ
以上を用いると、$a$ ごとに $N < f(x)$ がなりたつ $f(x)$ を列挙すれば良いです。そのような $x$ の数は $\Theta(\log(N))$ 通りしかないので、以下のように実装すれば全体の計算量は $\Theta(log^{2}(N))$ となります。
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #include <atcoder/modint> using mint = atcoder::modint998244353; void solve(){ int N; cin >> N; // 基底を列挙する vector<int> base; // 基底を全て求める。 // 2^a - 1 タイプ { int a = 0; while ((1 << (a + 1)) - 1 <= N) a++; if (N < (3ll << (a - 1))) base.push_back((1 << a) - 1); } // 普通のタイプ { for (int a = 0; (3ll << a) - 1 <= N; a++){ int tmp = (N - ((1 << a) - 1)); tmp >>= (a + 1); tmp <<= (a + 1); tmp += (1 << a) - 1; while (tmp != (1 << a) - 1 && N <= tmp + (1 << (a + 1))){ base.push_back(tmp), tmp -= (1 << (a + 1)); } } } sort(base.begin(), base.end()); reverse(base.begin(), base.end()); base.emplace_back(0); base.insert(base.begin(), N + 1); mint ans = 0; int A = ((N + 1) / 4) * 4; for (int i = 1; i < (int)base.size(); i++){ int L = base[i], R = min(A, base[i - 1]); if (L < R){ ans += (mint(2)).pow(N + 2 - L - i) - (mint(2)).pow(N + 2 - R - i); } } if (N % 4 == 2) ans += 1; if (N >= 3) ans -= 1; cout << ans.val() << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; rep(i, 0, t) solve(); }
計算量改善
基底に含まれる任意の値 $b$ に対して、$\frac{1}{2^{b}}$ が事前にわかっていれば、全体の計算量が $\Theta(\log(N))$ になります。$b$ の bit のずれが少ないことから、$\frac{1}{2^{b}}$ の列挙は時間計算量 $\Theta(\log(N))$ で求められます。よって、全体の計算量も $\Theta(\log(N))$ です。
おまけ
この基底の列は、rns_kwg さんの提出を見ると、以下のように求めることができます。
int up = 32 - __builtin_clz(N); vector<int> base = {N}; for (int i = 0, j; i < up; i = j + 1){ for (j = i; j < up; j++) if ((N >> j) & 1) break; int a = ((N >> j) << j) - 1; base.emplace_back(a); for (int k = i; k < j; k++) base.emplace_back(a ^ (1 << k)); } base.pop_back();
なぜこれでいいのかの理由はわかっていないです。
