概述

本题要求依次处理 ~q~ 次操作，每次给出一个正整数 ~k~，求出使当前 ~n~ 的二进制表示中从右往左数第 ~k~ 位变为 ~1~ 的最小非负增量 ~x~，每次操作后 ~n~ 更新为 ~n + x~，最后输出全部 ~x~ 之和。关键在于第 ~k~ 位的权值为 ~2^{k-1}~，只需取出 ~n~ 的低 ~k~ 位（即 ~n \bmod 2^k~）与它比较，就能在常数时间内直接算出每次的 ~x~，总复杂度为 ~O(q)~。

分析

核心观察

二进制中从右往左数第 ~k~ 位的权值是 ~2^{k-1}~，所以第 ~k~ 位是否为 ~1~ 完全由 ~n~ 的低 ~k~ 位决定，与更高的位无关。记 ~r = n \bmod 2^k~，则第 ~k~ 位为 ~1~ 等价于 ~r \ge 2^{k-1}~，第 ~k~ 位为 ~0~ 等价于 ~r < 2^{k-1}~。

思路

由于更高的位不影响第 ~k~ 位，每次操作只需关注低 ~k~ 位 ~r = n \bmod 2^k~。

当 ~r \ge 2^{k-1}~ 时第 ~k~ 位已经是 ~1~，无需任何改动，取 ~x = 0~ 就是最小值。

当 ~r < 2^{k-1}~ 时，要让第 ~k~ 位变成 ~1~，低 ~k~ 位至少要涨到 ~2^{k-1}~；而低 ~k~ 位每增大 ~1~，整个数也恰好增大 ~1~，因此增量不可能小于 ~2^{k-1} - r~。取

$$\displaystyle x = 2^{k-1} - r $$

时，低 ~k~ 位恰好变成 ~2^{k-1}~，即二进制下的 ~100\cdots0~（共 ~k~ 位，第 ~k~ 位为 ~1~、其余为 ~0~）。又因为 ~x < 2^{k-1} \le 2^k~，加上去不会向第 ~k+1~ 位进位，高位保持不变，所以这样的 ~x~ 既可行又最小。

两种情形可以统一写成

$$\displaystyle x = \max\left(0,\ 2^{k-1} - (n \bmod 2^k)\right) $$

算出后令 ~n \leftarrow n + x~，再处理下一次操作。

朴素做法是每次从当前 ~n~ 出发不断加 ~1~，直到第 ~k~ 位变成 ~1~，单次最坏需要约 ~2^{31}~ 次加法，~q~ 次的总运算量无法承受；利用低 ~k~ 位的性质可以把单次操作降到 ~O(1)~，总复杂度 ~O(q)~。

具体示例

样例中 ~n = 5~，~q = 3~，三次操作的 ~k~ 依次为 ~2, 3, 4~。

• 第 ~1~ 次操作，~k = 2~：~2^{k-1} = 2~，~r = 5 \bmod 2^2 = 1 < 2~，故 ~x = 2 - 1 = 1~，~n~ 变为 ~6~（二进制 ~110~）。
• 第 ~2~ 次操作，~k = 3~：~2^{k-1} = 4~，~r = 6 \bmod 2^3 = 6 \ge 4~，第 ~3~ 位已是 ~1~，故 ~x = 0~，~n~ 保持 ~6~。
• 第 ~3~ 次操作，~k = 4~：~2^{k-1} = 8~，~r = 6 \bmod 2^4 = 6 < 8~，故 ~x = 8 - 6 = 2~，~n~ 变为 ~8~。

三次增量之和为 ~1 + 0 + 2 = 3~，与样例输出一致。

算法步骤

1. 读入 n 与 q，初始化 sum 为 ~0~。
2. 重复 q 次，每次读入 k。
3. 令 pw 等于 ~2^{k-1}~，即第 ~k~ 位的权值；令 r 等于 ~n \bmod 2^k~，即 ~n~ 的低 ~k~ 位。
4. 若 r 小于 pw，则令 x 等于 pw 与 r 之差，把 x 累加进 sum，并令 n 增加 x；否则不做任何修改。
5. 输出 sum。

复杂度分析

• 时间复杂度：~O(q)~，每次操作只含常数次算术运算。
• 空间复杂度：~O(1)~，只需常数个变量。

实现注意事项

• ~n~ 可以取到 ~2^{32} - 1~，而 ~k = 32~ 时要用 ~2^{32}~ 取模，两者都超出了 ~32~ 位有符号整型的表示范围，读入 ~n~ 必须使用 ~64~ 位整型（long long）。
• 单次增量最大为 ~2^{31} - 1~（~k = 32~ 且 ~n \bmod 2^{32} = 1~ 时取到），在 ~q \le 10^5~ 次操作后总和的上界约为 ~2.1 \times 10^{14}~，同样超出 ~32~ 位整型的范围，因此累加变量 ~sum~ 也必须使用 ~64~ 位整型；若用 ~32~ 位整型累加，在 ~k = 32~ 的数据上会溢出回绕，得到错误答案。
• 计算 ~2^{k-1}~ 时要用 ~64~ 位的字面量参与移位，若用 ~32~ 位字面量左移，在 ~k~ 较大时结果就不是正确的权值了；~2^k~ 可由 ~2^{k-1}~ 直接左移一位得到，不必重复计算。
• 判断必须取严格小于：低 ~k~ 位小于 ~2^{k-1}~ 时才需要加增量，大于或等于时第 ~k~ 位已经是 ~1~，增量取 ~0~，容易写成非严格比较而多算。
• 输入最多 ~10^5~ 行，C++ 用 scanf 依次读入即可满足时限；Python 的整数为任意精度，不存在溢出问题，但建议一次性读入全部输入后再切分，以减少读入开销。

源代码

#include <cstdio>

int main() {
    long long n = 0, q = 0;
    scanf("%lld %lld", &n, &q);

    long long sum = 0;
    for (long long i = 0; i < q; ++i) {
        int k = 0;
        scanf("%d", &k);

        const long long pw = 1LL << (k - 1);  // 2^(k-1)，第 k 位的权值
        const long long r = n % (pw << 1);    // n mod 2^k，n 的低 k 位
        if (r < pw) {
            const long long x = pw - r;
            sum += x;
            n += x;
        }
    }

    printf("%lld\n", sum);
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    q = int(data[1])

    total = 0
    for i in range(q):
        k = int(data[2 + i])
        pw = 1 << (k - 1)          # 2^(k-1)，第 k 位的权值
        r = n % (pw << 1)          # n mod 2^k，n 的低 k 位
        if r < pw:
            x = pw - r
            total += x
            n += x

    print(total)


main()