题解 | 变化的数组

"""
import sys

MOD = 10 ** 9 + 7

# 了解了一下快速幂算法，二进制取幂能省下不少时间
def fast_pow(base, exp, mod):
    result = 1  # 初始结果
    while exp > 0:  # 当指数还没处理完
        if exp & 1:  # 检查 exp 的最低位是不是 1
            result = (result * base) % mod  # 是 1 就乘上去
        base = (base * base) % mod  # 底数平方（准备下一位）
        exp >>= 1  # 指数右移一位（去掉最低位）
    return result


def solve():
    line = sys.stdin.readline().split()
    n = int(line[0])
    m = int(line[1])
    k = int(line[2])

    line2 = sys.stdin.readline().split()
    a = []
    for i in range(n):
        a.append(int(line2[i]))

    S = 0
    for i in range(n):
        S = S + a[i]
    S = S % MOD

    T = 0
    for i in range(n):
        T = T + (a[i] & m)
    T = T % MOD


    # 计算 2^k mod MOD
    k_M = fast_pow(2, k, MOD)

    inv_k_M = fast_pow(k_M, MOD - 2, MOD) # MMP...这个逆元给我整麻了，华为机考总不能还带数学竞赛知识把...

    result = (S + (T * (k_M - 1) % MOD) * inv_k_M) % MOD #整体概率是1/2，但轮次不独立，所以得按照1/2+....1/(2^k)也就是1-1/(2^k)

    print(result)


if __name__ == "__main__":
    solve()

"""

MOD = 10 ** 9 + 7


def modinv(a):
    return pow(a, MOD - 2, MOD)


def solve():
    import sys

    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    a = list(map(int, data[3 : 3 + n]))

    # 预处理组合数系数，因为i很小，我们可以直接计算C(k,i) mod MOD
    # 由于k很大，需要循环乘
    # 先计算 inv2^k
    inv2 = modinv(2)
    inv2k = pow(inv2, k, MOD)

    # 预计算组合数 C(k, i) 对于 i=0..30
    comb = [0] * 31
    comb[0] = 1
    # 计算 C(k, i) = k*(k-1)*...*(k-i+1) / i!
    # 需要分母的逆元，可以预处理阶乘逆元
    # 由于i很小，直接乘除
    # 注意：k可能小于i？但i≤30，k≥1，所以没问题
    fact = [1] * 31
    for i in range(1, 31):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * 31
    inv_fact[30] = modinv(fact[30])
    for i in range(29, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    # 计算组合数
    # 由于k很大，我们直接用公式，注意取模
    # 注意：k可能大于MOD，但组合数公式在模意义下需要小心，因为k可能不是小于MOD，但这里k ≤ 1e9 < MOD，所以没问题
    comb[0] = 1
    for i in range(1, 31):
        # C(k,i) = C(k,i-1) * (k-i+1) / i
        comb[i] = comb[i - 1] * (k - i + 1) % MOD
        comb[i] = comb[i] * modinv(i) % MOD

    # 现在对于每个数，计算迭代序列
    ans = 0
    for x in a:
        seq = []
        cur = x
        while True:
            y = cur & m
            if y == 0:
                break
            seq.append(cur)
            cur = cur + y
        # 循环结束时，cur 是稳定值（即cur & m == 0）
        # seq 记录了每一步的值，长度记为 t
        t = len(seq)
        # 计算概率
        p_rest = 1
        exp_val = 0
        for i in range(t):
            p_i = comb[i] * inv2k % MOD
            exp_val = (exp_val + seq[i] * p_i) % MOD
            p_rest = (p_rest - p_i) % MOD
        exp_val = (exp_val + cur * p_rest) % MOD
        ans = (ans + exp_val) % MOD

    print(ans)


if __name__ == "__main__":
    solve()

不说了，给我整抑郁了....真有你的HW