hihoCoder Challenge 33 C - 加减

题目大意

定义对正整数 $x$ 的一次变换为:有 $1/2$ 的概率变成 $x+\operatorname{lowbit}(x)$,$1/2$ 的概率变成 $x-\operatorname{lowbit}(x)$。
定义 $f(x)$ 表示正整数 $x$ 变换为 $0$ 的期望步数。
给定 $L,R$,求 $\sum_{x=L}^Rf(x)$。

$0\leq L\leq R\lt 2^{31}$


题目分析

考虑计算 $f$ 的前缀和。

乍一看加加减减的,似乎一个数操作若干次会变回来,其实不然。
仔细分析性质,我们可以发现:
$\bullet$ 不管是 $+\operatorname{lowbit}$ 还是 $-\operatorname{lowbit}$,过程虽然是曲折的,数值可能会变大变小,但是后缀连续零是前进的,每次操作后严格递增的。(被学业水平测试带跑的哲学语气)
$\bullet$ 一个位置最多只会被进位一次。

因此我们可以考虑一个从低位往高位的数位 $dp$,令 $f_{i,j,k}$ 表示 $0…i-1$ 位上都已经变成了 $0$,当前这一位是(否)有来自 $i-1$ 的进位,以及 $0…i-1$ 组成的二进制数是(否)小于上界这些位置对应的二进制数情况下的期望,为了转移,我们还要类似地记录这种情况的概率。
转移很简单,直接考虑这一位填什么,简单讨论就好了。

现在还有一个问题就是我们可能在填完所有位之后,依然有进位。注意到这个时候只有这一个最高位的 $1$,利用简单的期望知识就可以得到它能在期望 $2$ 步内被删除,我们统计这种情况出现的概率乘上 $2$ 就能处理了。
时间复杂度 $O\left(\log(R)\right)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

const int P=998244353;
const int itwo=P+1>>1;
const int L=31;

inline void add(int &x,int y){x=x+y>=P?x+y-P:x+y;}

int f[L+5][2][2],g[L+5][2][2];//expectation probability

inline int dp(int n)
{
if (n<=0) return 0;
memset(f,0,sizeof f),memset(g,0,sizeof g);
g[0][0][1]=1;
for (int i=0,d;i<L;++i)
{
d=n>>i&1;
for (int j=0;j<2;++j)
for (int k=0,exp,pro;k<2;++k)
if (f[i][j][k]||g[i][j][k])
{
exp=f[i][j][k],pro=g[i][j][k];
for (int x=0;x<2;++x)
{
bool k_=x<d||(k&&x==d);
if (j^x)
{
int dexp=1ll*itwo*(pro+exp)%P,dpro=1ll*itwo*pro%P;
//+lowbit
add(f[i+1][1][k_],dexp),add(g[i+1][1][k_],dpro);
//-lowbit
add(f[i+1][0][k_],dexp),add(g[i+1][0][k_],dpro);
}
else add(f[i+1][j&&x][k_],exp),add(g[i+1][j&&x][k_],pro);
}
}
}
return (2ll*g[L][1][1]+f[L][0][1]+f[L][1][1])%P;
}

int l,r;

int main()
{
freopen("lowbit.in","r",stdin),freopen("lowbit.out","w",stdout);
scanf("%d%d",&l,&r),printf("%d\n",(dp(r)-dp(l-1)+P)%P);
fclose(stdin),fclose(stdout);
return 0;
}