UOJ Logo poorpool的博客

博客

#103. 割海成路之日 题解

2018-03-08 08:53:39 By poorpool

本文整理自flyinghearts的博客。

记 $f(x,y)$ 为从 $x$ 一路异或到 $y$ 的值。$\mathrm{xor}$ 异或,$\mathrm{or}$ 是或。

对于 $f(2^k,2^{k+1}-1)$ 这 $2^k$ 个数,它们的最高位显然是第 $k$ 位。最高位的 $1$ 的个数为 $2^k$。

$k \geq 1$ 时, $2^k$ 为偶数,$\mathrm{xor}$ 下来成了 $0$。将这些数的最高位抹去,$f$ 的值不变,则 $f(2^k,2^{k+1}-1)=f(2^k-2^k,2^{k+1}-1-2^k)=f(0,2^k-1)$。

则 $f(0,2^{k+1}-1) = f(0,2^k-1)\ \mathrm{xor}\ f(2^k,2^{k+1}-1)=0$ 当 $k \geq 1$ 时。

即 $f(0,2^k-1)=0$ 当 $k \geq 2$ 时。


对于 $n \geq 4$,设其最高位 $1$ 在第 $k$ 位,则 $k \geq 2$。

$f(0,n)=f(0,2^k-1)\ \mathrm{xor}\ f(2^k,n)=f(2^k,n)$

对于 $2^k \sim n$ 这 $n-2^k+1$ 个数,最高位有 $m=n-2^k+1$ 个 $1$。

$n$ 与 $n-2^k$ 同奇偶。

  • 当 $n$ 为奇数时

$m$ 是偶数,则 $f(2^k,n)=f(0,n-2^k)$。

递降这个公式,也即相当于不断剥去 $n$ 最高位的 $1$,得到 $f(0,n)=f(0,n \bmod 4)$。

$n \equiv 1 \pmod 4$ 时,$f(1,n)=f(0,n)=f(0,1)=1$。

$n \equiv 3 \pmod 4$ 时,$f(1,n)=f(0,n)=f(0,3)=0$。

  • 当 $n$ 为偶数时

$m$ 是奇数,则 $f(2^k)=f(n-2^k)\ \mathrm{or}\ 2^k$。

递降这个公式,得 $f(0,n)=\eta\ \mathrm{or}\ f(0,n \bmod 4)$。

其中 $\eta$ 是 $n$ 将第 $0,1$ 位置 $0$ 后的数。

$n \equiv 0 \pmod 4$ 时,$f(1,n)=f(0,n)=n$。

$n \equiv 2 \pmod 4$ 时,$f(1,n)=f(0,n)=n+1$。

综上所述 $$ f(1,n)= \begin{cases} n, &n \equiv 0 \pmod 4\\ 1, &n \equiv 1 \pmod 4\\ n+1, &n \equiv 2 \pmod 4\\ 0, &n \equiv 3 \pmod 4\\ \end{cases} $$

因此我们得到了 $\mathrm{O}(1)$ 算法

评论

Capella
%%%%%
NaCl
真是大神啊 qwq 某翎只是打印了前 100 个值然后人工找规律…

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。