题解 UVA1406 【实验法计算概率 A Sequence of Numbers】
皎月半洒花
2019-07-22 09:36:54
## $\rm{Sol~of~UVa1406}$
个人认为是一道思路比较清新的题。
以下对于二进制位の一切描述均基于国人的阅读习惯，从高位向低位曰“从前向后”。
首先我们考虑一步转化，即对于询问的$k$，假设我们只保留后$k-1$位，我们会发现信息并不会缺失，因为高位的加减法不影响低位，换句话说这就启发我们要用前缀和维护一下：
```cpp
_bit[0] = 1 ;
for (i = 1 ; i <= 16 ; ++ i) _bit[i] = _bit[i - 1] << 1 ;
for (i = 1 ; i <= N ; ++ i){ scanf("%d", &x) ;
for (j = 1 ; j <= 16 ; ++ j)
Sum[j - 1][x % _bit[j]] ++ ;
}
for (i = 0 ; i <= 16 ; ++ i)
for (j = 1 ; j <= (1 << 16) ; ++ j)
Sum[i][j] += Sum[i][j - 1] ;
```
如上，我们考虑对于每个$Input_i$，我们令它对$2$的次幂们取模，而众所周知$w \bmod 2^k=(w~\rm{and}~ (2^k-1))$，换句话说也就是保留了后$k-1$位。
之后我们考虑，我们其实是在解一个形式化的方程：
$$
\rm{Sum+x=2^k+b}\quad (0\leq b<2^k)
$$
其中$\rm{Sum}$表示我们已经累加过的`Add`操作的和。
同时，由于我们已经通过分类前缀和解决了$k$位以及$k$位之前的一切问题，我们只需要对后$k-1$位分类讨论：
* 假设$\rm{Sum~and}~2^k=0$，那么显然最后在$\bmod~2^k$的条件下，我们的$2^k+b$应该取$[2^k, 2^{k+1}-1]$，直接前缀和就好了。
* 假设$\rm{Sum~and}~2^k=1$，那么我们考虑两种情况：
* 第$k-1$位不产生进位。那么显然必须也要有第$k$位**不产生进位**才能保证第$k$位是$1$，那么也就是说会有$x+\rm{Sum}\leq 2^{k-1} \bmod~2^k$，直接前缀和计算一下就好；
* 第$k-1$位产生进位。那么显然必须也要有第$k$位**产生进位**才能保证第$k$位是$1$。故我们考虑此时实际上$x$最多可以取到$2^{k}-1$，最少也必须满足$2^k-1-\rm{Sum}$，故前缀和一下就完了。
```cpp
while (scanf("%s", s) && s[0] != 'E'){
scanf("%d", &x) ;
if (s[0] == 'Q'){
int Done = S % _bit[x] ;
if (!(S & _bit[x])) Ans += Sum[x][_bit[x + 1] - Done - 1] - Sum[x][_bit[x] - Done - 1] ;
else Ans += Sum[x][_bit[x] - 1 - Done] + Sum[x][_bit[x + 1] - 1] - Sum[x][_bit[x + 1] - 1 - Done] ;
}
else (S += x) %= Mod ;
}
printf("Case %d: %lld\n", _case, Ans) ;
```