题解 | 变化的数组

import sys
def input(): return sys.stdin.readline().strip()

MOD = 10**9 + 7

MAXI = 31
fac = [1] * (MAXI + 1)
ifac = [1] * (MAXI + 1)
for i in range(1, MAXI + 1):
    fac[i] = fac[i - 1] * i % MOD
ifac[MAXI] = pow(fac[MAXI], MOD - 2, MOD)
for i in range(MAXI, 0, -1):
    ifac[i - 1] = ifac[i] * i % MOD

def comb(k, i):
    """
    C(k,i) = k*(k-1)*...*(k-i+1) / i!
    """
    if i < 0 or i > k: return 0
    num = 1
    for j in range(i):
        num = num * ((k - j) % MOD) % MOD
    return num * ifac[i] % MOD

def build_seq(x, m, k):
    L = [x]
    for _ in range(k):
        nxt = L[-1] + (L[-1] & m)
        if nxt == L[-1]:
            break
        L.append(nxt)
    return L

def expected_one(x, m, k):
    L = build_seq(x, m, k)
    T = len(L) - 1  # 序列最后一个有效下标

    Cki = [comb(k, i) for i in range(T)]
    pow2k = pow(2, k, MOD)
    inv2k = pow(pow2k, MOD - 2, MOD)
    prob = 0
    exp = 0
    for i in range(T):
        prob = (prob + Cki[i]) % MOD
        exp = (exp + L[i] * Cki[i]) % MOD

    rest_prob = (pow2k - prob) % MOD
    numerator = (exp + L[T] * rest_prob) % MOD

    return numerator * inv2k % MOD

# ---- 主流程 ----
n, m, k = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for a in A:
    ans = (ans + expected_one(a, m, k)) % MOD
print(ans)