题目：

“好串”是指由 0 和 1 组成的形如 $ABABA\dots A$ 或 $ABABA\dots AB$ 的二进制串。其中 $A$ 是连续 $k$ 个 1，$B$ 是连续 $g$ 个 0。其中 $k,g \ge0$。

求 $[l,r]$ 中由多少个数的二进制表示是“好串”。

注意 0 不是“好串”。

$l\le r \le 2^{63}$。

思路：

感觉可以用一个类似前缀和的东西来做，就是求 $s_r-s_{l-1}$。

而有 $i$ 位的“好串”个数貌似是这个，不过还是不知道如何求 $s_x$。