变化的数组

package main

import (
	"bufio"
	"fmt"
	"os"
)

/* 
	分别求每一个数的期望
	其中，考虑到and的性质，一个数变化一定次数后，值会变为0，后续值不再改变
 */

const MOD = 1000000007

// 快速幂：计算 (base^exp) % MOD
func powMod(base, exp, mod int64) int64 {
	var result int64 = 1
	for exp > 0 {
		if exp&1 == 1 {
			result = (result * base) % MOD
		}
		base = (base * base) % MOD
		exp >>= 1
	}
	return result
}

// 计算 C(k, t) mod MOD，k 可能很大，但 t 很小
func comb(k, t int64) int64 {
	/*
		费马小定理
		MOD为质数，den != 0，den^(MOD-1) = 1 (mod MOD)
		den模MOD为1的逆为(den^(MOD-2))%MOD
	*/
	if t == 0{
		return 1
	}
	if t < 0 || k < t  {
		return 0
	}

	var m, n int64 = 1, 1 // 分子、分母
	for i := int64(0); i < t; i++ {
		m = m * ((k - i) % MOD)% MOD
		n = n * (i + 1) % MOD
	}
	n_ := powMod(n, MOD-2, MOD)
	return m * n_ % MOD
}

// 模拟一个数 x 在操作下的演化路径
func evolvePath(x, m int64) []int64 {
	path := []int64{}
	for {
		path = append(path, x)
		andVal := x & m
		if andVal == 0 { // 变化一定次数后会变为0
			break
		}
		x = x + andVal
	}
	return path
}

// 计算单个数 x 经过 k 次操作后的期望值
func expectedOne(x, m, k int64) int64 {
	path := evolvePath(x, m)
	var T int64 = int64(len(path))

	var num2k int64 = powMod(2, k, MOD)
	var num2k_ int64 = powMod(num2k, MOD-2, MOD)

	var result, front, t int64 = 0, 0, 0
	for i := int64(0); i < T-1; i++ { // 前T-1个,
		t = comb(k, i)
		result = (result + path[i] * t) %MOD
		front = (front + t)%MOD
	}

	result = (result + path[T-1] * ((num2k - front+MOD)%MOD)) % MOD
	return result * num2k_ % MOD
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m, k int64
	fmt.Fscanf(reader, "%d %d %d\n", &n, &m, &k)

	var a = make([]int64, n)
	for i := int64(0); i < n; i++ {
		fmt.Fscanf(reader, "%d", &a[i])
	}

	var result int64 = 0
	for i := int64(0); i < n; i++ {
		result = (result + expectedOne(a[i], m, k)) % MOD
	}

	fmt.Println(result)
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final long[] p = new long[32];


    static long fast_pow_mod(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0)
                res = (long) res * a % p;
            a = (long) a * a % p;
            b >>= 1;
        }
        return res;
    }

    public static long C(int a, int b) {
        if (a < b)
            return 0;
        long res = 1;
        for (long i = 1, j = a; i <= b; j--, i++) {
            res = (long) res * j % MOD;
            res = (long) res * fast_pow_mod(i, MOD - 2, MOD) % MOD;
        }
        return res;
    }

    public static long solve(int[] list, int n, int m, int k) {
        for (int i = 0; i < 31; i++) {
            p[i] = C(k, i) * fast_pow_mod(fast_pow_mod(2, k, MOD), MOD - 2, MOD) % MOD;
            p[31] = (p[31] + MOD - p[i]) % MOD;
        }
        p[31] = (1 + p[31]) % MOD;

        long res = 0, x;
        for (int i = 0; i < n; i++) {
            x = list[i];
            for (int j = 0; j < 32; j++) {
                res += x * p[j] % MOD;
                res %= MOD;
                x += x & m;
            }
        };
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = in.nextInt();
        }

        System.out.println(solve(list, n, m, k));
    }
}