笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 UVA1406 【实验法计算概率 A Sequence of Numbers】

posted on 2019-07-22 09:36:54 | under 题解 |

$\rm{Sol~of~UVa1406}$

个人认为是一道思路比较清新的题。

以下对于二进制位の一切描述均基于国人的阅读习惯,从高位向低位曰“从前向后”。

首先我们考虑一步转化,即对于询问的$k$,假设我们只保留后$k-1$位,我们会发现信息并不会缺失,因为高位的加减法不影响低位,换句话说这就启发我们要用前缀和维护一下:

_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}$,故前缀和一下就完了。
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) ;