变化的数组

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

题目描述： 我们对一个数组当中的每一个元素抛硬币，如果硬币是正面，那就把这个数和一个特定的数做“和”运算，就是按位运算的和运算，如果不行，那就保留这个数本身。当我们做了K次这种运算（每一次都是对数组中全部的数的运算），而后对k次运算后的每一个值的期望值求和。

算法： 本题是要求二次分布的期望。我们可以换个思路，其实是对每一个硬币都要做k次实验。所以就是对每个值做了k次实验以后的期望值的求和。那么就是一个二项分布，对每一个数有k次的硬币实验，然后k次实验会有一个二项分布的期望值。

所以对每一个数来说，k次实验以后的期望值如上图所示。分子中的组合数代表k次实验中有n次硬币是正面的次数。result代表n次是正面的时候，数的变化。 分母是抛k次硬币中所有的正反组合的情况。求得每个数的结果以后，对所有的数的期望值求和就是最终的结果。但是题目要求我们进行模运算。我们要在模的框架下得到所有的结果。

模运算： A ≡ B mod C . A与B同余，即A mod C = B mod C。 (A+B) mod C = (AmodC + BmodC) modC。减法和乘法同加法。 (A^B) modC = ((AmodC)^B ) modC 。 A/B = ( A * B_inv ) mod C。B inv就是在modC的情况下B的倒数。这个需要通过费马小定理求。B_inv = (B^(C-2) )mod C. 在python中求B_inv = pow(B, C-2 , C)。 在模运算的情况下，求C(k,n)需要使用inv，即 C(k,n) = K! / n! *(k-n)! = k! * (n!)_inv * (k-n!)_inv. 其中，n!_inv = (n-1)!_inv * n_inv. n_inv = 1/n。即 n!_inv * n = (n-1)!_inv。 n!_inv = n! ^ C-2。

最后一个点就是，一个数在通过位求和累加了一定的次数以后就不会变了，这个次数可以设定位30. 所以1式可以改写为

当然我们可以将这个式子改写为使用模倒数的形式。

import sys 
a = sys.stdin 
b = next(a).strip().split(' ')
n = int(b[0])
m = int(b[1])
k = int(b[2])
x = [int(i) for i in next(a).strip().split(' ')]

M = 10 ** 9 + 7
maxFac = 32
# 不知道为啥，把定义放一起就会节省时间
fac = [1] * maxFac
ifac = [1] * maxFac
# 0 ~ 31 的阶乘 , 开头要放1， 因为计算组合数的时候是从0开始算的，即c(k,0),1对应0的阶乘。
for i in range(1, maxFac):
    fac[i] = fac[i - 1] * i % M

# 0 ~ 31 的阶乘的模倒数/ 通过逆序公式求得(g)(h)
ifac[maxFac - 1] = pow(fac[maxFac - 1], M - 2, M)

for i in range(maxFac - 1, 0, -1):
    ifac[i - 1] = ifac[i] * i % M

# 计算模框架下的组合数， K 是总的次数，n是抽取的次数 (b); K<=31
# k-n也有可能超过模的范围，所以需要模一下 i%M
def combination(k, n):
    res = 1
    for i in range(k, k - n, -1):
        res = res * (i % M) % M
    res = res * ifac[n] % M
    return res
 

# 计算期望，对应 (a)
def calcuProb(x, m, k):
    # 首先判断在几次正面硬币之后，数值再求和不变
    valueList = [x]
    for _ in range(32):
        value = valueList[-1] + (valueList[-1] & m)
        if value == valueList[-1]:
            break
        else:
            valueList.append(value)

    # 分母要取模倒数
    powK = pow(2, k, M)
    invPowK = pow(powK, M - 2, M)
    # 分子中，在变化范围内的，都要单独计算次数，正面的次数从0开始
    # 不变的时候，统一认为数值是valueList[-1]，次数是总次数减变化的次数
    # combination 加起来可能会超模，所以模一下
    expTemp = 0
    sumCombination = 0
    expTemp2 = 0
    for i in range(0, len(valueList)-1):
        combNum = combination(k, i) 
        expTemp =  ( expTemp + (combNum * valueList[i] % M) ) % M
        sumCombination = (sumCombination +  combination(k, i)) % M
    times  = (powK - sumCombination)  % M
    expTemp2 = (expTemp +  times * valueList[-1]) % M
    res =  expTemp2  * invPowK % M
    return res

finalRes = 0 

for i in x:
    finalRes = ( finalRes + calcuProb(i, m, k) ) % M 
print(finalRes)

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