题解 | 变化的数组

运行时间超时了，但是不提示超时。

def ksm(a, b):  # 快速幂 计算 a ** b
    s = 1
    while b:
        if b & 1:
            s = s * a % MOD
        a = a * a % MOD
        b >>= 1
    return s


def cal(n, m):  # 计算组合数 C n m
    # 组合数C n m = n ! / (m ! * (n - m)!)
    # 费马小定理：如果 p 是一个质数，那么对于任何整数 a：a ** (p - 1) = 1 mod p
    # 由此推导出模逆元计算公式： a ** （-1） = a ** (p - 2) mod p
    # 利用模逆元计算公式，将组合数计算中的除法转换成乘法，并避免数值溢出
    if m > n - m:  # 组合数的对称性
        m = n - m
    ans = 1
    for i in range(1, m + 1):
        ans = ans * (n - m + i) * ksm(i, MOD - 2) % MOD
    return ans


while True:
    try:
        n, m, k = map(int, input().split())
        num = list(map(int, input().split()))
        MOD = 1000000007
        # 对于一个num[i]和m，按二进制来看，num[i] & m 的最低位的1 和 num[i] 相加后，会变0进位，更低位的值不会变化
        # 下一次num[i] & m 的1的最低位将会变高
        # 当num[i]的1最低位比m的1最高位还高时，num[i]的值将不会发生变化
        length = len(bin(m)[2:])
        p = [0] * (length + 2)  # num[i]的变化情况 比 m的二进制位数 多2
        for i in range(length + 1):  # 变化i次的概率为 C k i / 2 ** k
            p[i] = cal(k, i) * ksm(ksm(2, k), MOD - 2) % MOD
            p[-1] += MOD - p[i]
        p[-1] = (1 + p[-1]) % MOD    # 变化次数 大于 m的二进制位数 时，num[i]不变

        ans = 0
        for i in range(n):
            for j in range(length + 2):
                ans = ans + num[i] * p[j] % MOD
                ans %= MOD
                num[i] += num[i] & m
                # 这里不能写成 num[i] = num[i] + num[i] & m ， 因为 + 比 & 优先级高
        print(ans)
    except:
        break