# 2019交大年度賽pL非官方題解

###### tags: `PCCA`
> NCTU_Pusheen
> Edited by Luke2336

## 題意

將L到R (0~1e9) 的二進位字串接起來，然後求這個字串連續的1和0共有幾段。
例如1~5，表示成1 10 11 100 101，(11)(0)(111)(00)(1)(0)(1)，答案為7。

## 卡車的解法

關鍵觀察一：固定 Prefix $p$ 時，後面接上 $k$ 個 random bits 的 binary string 的段數期望值在均勻分佈下，是 $p$ 的段數加上 $\frac{k}{2}$。
關鍵觀察二：把所有可能出現的 random bits 拿出來加總平均就是期望值，因此可以用個數乘上期望值獲得一些數字的內部總段數。

剩下來的工作就是看銜接的部份要怎樣扣除與調整。如果要求 $b$ 開始到 $e$ 為止的串接總段數，可以用從 $0$ 到 $e$ 的段數扣掉 $0$ 到 $b-1$ 的段數，再看 $b$ 是 $0$、正奇數、正偶數來調整。我們就聚焦於如何算 $0$ 到 $x$ 接起來的總段數，$x=0$ 跟 $x=1$ 的部份大家可以手算。

我們可以把 $0$ 到 $x$ 這段數字依據 bit 數拆開來看：如果為 $k$-bit 的 binary string 一定長成 $1$ 後面接 $k-1$ 個 bits，而透過前面的觀察，這些的內部總段數為 $\left(1+\frac{k-1}{2}\right)2^{k-1}=\left(1+k\right)2^{k-2}$段。把這總共 $2^{k-1}$ 個串起來，則數字之間會黏掉奇數後接偶數的那些$1$，總共 $2^{k-2}-1$ 個。最後把這堆東西接到長度 $(k-1)$-bit的字串後面，會再黏掉一個，因此總貢獻$k2^{k-2}=\frac{k2^k}{4}$。以此觀察，我們就會算 $0$ 到 $2^{k}-1$ (二進位長成 $1\cdots111$) 這種格式的資料了。這部份的 code 在 18 行。

接下來，如果 $x$ 是個偶數，那麼我們就考慮先算 $0$ 到 $x-1$ ，再把 $x$ 黏上去，這一部份寫在 20 行。為何偶數要拔出來先算是因為這個 case 沒有辦法套 random bit 的觀察，但其實很簡單算。

最後，如果 $x$ 是個奇數，那麼我們就考慮把最後面的那堆 $1$ 給拔掉(假定有 $k$ 個)，先算這部份出來。當 $x$ 拔掉那 $k$ 個 $1$ 之後，得到$z$。先算出 $0$ 到 $z-1$ 的部份，再把 $z$ 到 $x$ 黏上去。這時候套用觀察，我們得知這些數字的內部段數等同於每個數字平均貢獻 $z$ 的段數加上 $\frac{k}{2}$。最後再補正黏接偶數到奇數後面損失的段數，就得到答案了。

複雜度：$O(\log^2n)$，這邊長出 Binary string 後面硬幹段數花 $O(\log n)$ 比較痛。

private fun nextLine() = readLine()!!
private fun nextToks() = nextLine().split(" ").filter{it.length > 0}
private fun nextLongs() = nextToks().map{it.toLong()}

fun runs(x: String) = /* calculate number of runs */
    x.mapIndexed{i, c -> if (i==0 || c!=x[i-1]) 1 else 0}.sum()

fun runs(x: Long) = runs(x.toString(2)) // call String version

fun Long.log2() = this.toBigInteger().bitLength() - 1 // lazy

fun pre(x: Long): Long {
    if (x < 0L) return 1                     // take care of b = 0
    if (x < 2L) return x+1                   // terminal cases
    val y = x + 1
    val lowbit = y.and(-y)
    if (y == lowbit)                         // x is in the form: 11...111
        return pre(x / 2) + y.log2() * y / 4
    if (lowbit == 1L)                        // x is in the form: 1?...??0
        return pre(x - 1) + runs(x) - 1
    val z = y - lowbit                       // x is in the form: 1?...?011...1
    return pre(z - 1) + runs(z) * lowbit + (lowbit.log2()-1) * lowbit / 2
}

fun main() {
    val (b, e) = nextLongs()
    println("${pre(e) - pre(b - 1) + 1 - (b%2)}")
}

## Pusheen的解法

1. 可以觀察到：
奇數接偶數時，是1和1相接
偶數接奇數時，是0和1相接
發現只要算出每個數裡面0和1的片段數，求和，最後再扣掉11相接的數量就行了。

2. 如下表：
f(x)為x中的片段數，觀察二進位對稱性可得到f(x)的遞迴式。
再觀察得到s(2^k-1) 也就是 sum(f(1)~f(2^k-1))的公式。

s(2^k-1) = s(2^(k-1)-1) * 2 + 2^(k-1)。

開個陣列把這些預處理起來，空間O(lgN)。


3. 考慮f(L)~f(R\)的和，明顯可用s(R\)-s(L-1)處理。但L==0要額外處理。

4. s(x)的算法：
若x剛好是2^k-1，則直接用預處理的那些s。
最後考慮切不完整的部分，可遞迴處理，時間O(lgN)，以s(12)為例。

s(12) = s(15) - s(15-12-1) - (15-12) = s(15) - s(2) - 3
s(2) = s(7) - s(3-2-1) - (3-2) = s(7) - s(0) - 1

5. 最後扣掉[L,R]中「後面有偶數的奇數」個數。然後就跟隊友打個架，就AC了?