题解 | 变化的数组

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)
}