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

皎月半洒花 · 2019-07-22 09:36:54 · 题解

\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}表示我们已经累加过的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) ;